# Double Feature on Christmas Day

Feature One (Pascal’s Identity): $\binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}\quad\quad\quad(1)$

Proof :

By definition, $\binom{n-1}{r-1} + \binom{n-1}{r}$ $= \frac{(n-1)!}{(n-1-(r-1))!(r-1)!} + \frac{(n-1)!}{(n-1-r)!r!}$ $= \frac{(n-1)!}{(n-r)!(r-1)!} + \frac{(n-1)!}{(n-1-r)!r!}$ $=\frac{r(n-1)!}{(n-r)!r(r-1)!} + \frac{(n-1)!(n-r)}{(n-r)(n-r-1)!r!}$ $= \frac{r(n-1)!}{(n-r)!r!} + \frac{(n-1)!(n-r)}{(n-r)!r!}$ $=\frac{(r + n-r)(n-1)!}{(n-r)!r!}$ $=\frac{n(n-1)!}{(n-r)!r!}$ $= \frac{n!}{(n-r)!r!}$ $= \binom{n}{r}$.

Feature Two (Binomial Theorem): $(a+b)^n = \sum\limits_{r=0}^{n}\binom{n}{r}a^{n-r}b^r\quad\quad\quad(2)$

Proof : $(a+b)^1 = a+b, \sum\limits_{r=0}^{1}a^{1-r}b^r = a+b \implies (a+b)^n=\sum\limits_{r=0}^{n}a^{n-r}b^r, n=1$.

If $(a+b)^{k-1} = \sum\limits_{r=0}^{n}\binom{k-1}{r}a^{k-1-r}b^r$ then $(a+b)^k = (a+b)(a+b)^{k-1} = (a+b)\sum\limits^{k-1}_{r=0}\binom{k-1}{r}a^{k-1-r}b^r$ $= \sum\limits^{k-1}_{r=0}\binom{k-1}{r}a^{k-r}b^r + \sum\limits^{k-1}_{r=0}\binom{k-1}{r}a^{k-1-r}b^{r+1}$ $=a^k + \sum\limits^{k-1}_{r=1}\binom{k-1}{r}a^{k-r}b^r +\sum\limits^{k-2}_{r=0}\binom{k-1}{r}a^{k-1-r}b^{r+1} +b^k$ $=a^k + \sum\limits^{k-1}_{j=1}\binom{k-1}{j}a^{k-j}b^j +\boxed{ \sum\limits^{k-2}_{r=0}\binom{k-1}{r}a^{k-1-r}b^{r+1}} +b^k$ $\boxed {j=r+1\implies r = j-1, r:0\rightarrow k-1\implies j:1 \rightarrow k-1}$ $=a^k + \sum\limits^{k-1}_{j=1}\binom{k-1}{j}a^{k-j}b^j+\sum\limits^{k-1}_{j=1}\binom{k-1}{j-1}a^{k-1-(j-1)}b^{(j-1)+1} +b^k$ $=a^k + \sum\limits^{k-1}_{j=1}(\boxed{\binom{k-1}{j}+\binom{k-1}{j-1}}) a^{k-j}b^j +b^k$ $\overset{(1)}{=}a^k + \sum\limits^{k-1}_{j=1}{\binom{k}{j}a^{k-j}b^j}+b^k$ $\overset{\binom{k}{0}=1, \binom{k}{k}=1}{=}\binom{k}{0}a^{k-0}b^0+\sum\limits^{k-1}_{j=1}\binom{k}{j} a^{k-j}b^j +\binom{k}{k} a^{k-k}b^k$ $= \sum\limits^k_{j=0}\binom{k}{j}a^{k-j}b^j$.

Exercise-1 Prove $\binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n-1} + \binom{n}{n} = 2^n-1$. hint: $2 = 1+1$

Exercise-2 Prove $1-\binom{n}{1} + \binom{n}{2} - \dots +(-1)^{n-1}\binom{n}{n-1} +(-1)^n = 0$.

Exercise-3 Generate

I think I shall never see
A poem as lovely as a tree – Joyce Kilmer

hint: (1)