More algebraic BinomialCoefficients hacking
∑ (n choose k) = (1+1)n = 2n
∑ (-1)k (n choose k) = (1-1)n = 0 [for n > 0]
General trick: GeneratingFunctions
Use F(z) = ∑ an zn to represent sequence a0 ...
Example: 1/(1-z) = ∑ zn represents 1, 1, 1, 1, 1, ...
Proof: use binomial theorem with (-1 choose n) = (-1)n
Note: this proof blew out in lecture, the problem was that I tried doing (1-z)-1 = ∑ (-1 choose n) z-1-n1n instead of the much more sensible ∑ (-1 choose n) (-1)-1-nzn. 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
Extract a0 with F(0)
(an+bn) represented by F+G
- Can also multiply by constants
- Shift right with zF
- Shift left with (1/z)(F - F(0))
Convert an to n an 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,...