More algebraic BinomialCoefficients hacking

• ∑ (n choose k) = (1+1)ⁿ = 2ⁿ

• ∑ (-1)^k (n choose k) = (1-1)ⁿ = 0 [for n > 0]

General trick: GeneratingFunctions

• Use F(z) = ∑ a_n zⁿ to represent sequence a₀ ...

• Example: 1/(1-z) = ∑ zⁿ represents 1, 1, 1, 1, 1, ...

  • Proof: use binomial theorem with (-1 choose n) = (-1)ⁿ

    • Note: this proof blew out in lecture, the problem was that I tried doing (1-z)^-1 = ∑ (-1 choose n) z^-1-n1ⁿ instead of the much more sensible ∑ (-1 choose n) (-1)^-1-nzⁿ. See the notes on BinomialCoefficients for what happens in both cases.

• Example: 1 represents 1, 0, 0, 0, 0, ...
• If two functions are equal, their coefficients are equal.
• Caveat: we should be worrying about convergence, but aren't

  • Excuse: these are really formal power series rather than genuine sums

Manipulating GeneratingFunctions

• Extract a₀ with F(0)

• Linearity

  • (a_n+b_n) represented by F+G

  • Can also multiply by constants
• Shifting
  • Shift right with zF
  • Shift left with (1/z)(F - F(0))
• Differentiation

  • Convert a_n to n a_n with z d/dz F

  • E.g. z d/dz 1/(1-z) gives g.f. for 0,1,2,3,...
  • Repeat to get 0,1,4,9,16,...