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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s