December 2019

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-2\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)

Month: December 2019