More algebraic BinomialCoefficients hacking

∑ (n choose k) = (1+1)

^{n}= 2^{n}∑ (-1)

^{k}(n choose k) = (1-1)^{n}= 0 [for n > 0]

General trick: GeneratingFunctions

Use F(z) = ∑ a

_{n}z^{n}to represent sequence a_{0}...Example: 1/(1-z) = ∑ z

^{n}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-n}1^{n}instead of the much more sensible ∑ (-1 choose n) (-1)^{-1-n}z^{n}. 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

_{0}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,...