As we are learning about mathematical induction, in this post, we are going to use induction to prove the following:
- formula for the Pascal's triangle $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
- the binomial identity $$(x+y)^n = x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$
Pascal's triangle is the following number pattern
this triangle is constructed based on the rule that any number inside the triangle is equal to the sum of two numbers sitting above it in the previous row
If we give the rows and the numbers on each row index numbers starting from 0
and use $p_{n,k}$ to denote the number of index $k$ on the row $n$ then the formula to construct the Pascal's triangle is $$p_{n-1,k-1} + p_{n-1,k} = p_{n,k}.$$
Now, we will prove by induction the following formula $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
For $n=0$, we have $$p_{0,0} = 1 = \frac{0!}{0!0!}$$ so the formula is correct for the case $n=0$. Just note that $0!$, by convention, is equal to $1$, not $0$.
Suppose that the formula is correct for any $0 \leq n \leq N$. We will prove that the formula is also correct for the case $n=N+1$.
Indeed, when $k=0$ or $k=N+1$ we have $$p_{N+1,0} = p_{N+1,N+1} = 1 = \frac{(N+1)!}{0! (N+1)!} = {{N+1} \choose 0} = {{N+1} \choose {N+1}}$$
When $1 \leq k \leq N$, we have $$p_{N+1,k} = p_{N,k-1} + p_{N,k}$$
By induction assumption, the formula is correct for the case $n=N$, so $$p_{N,k-1} = {N \choose {k-1}} = \frac{N!}{(k-1)! (N-k+1)!}, \quad p_{N,k} = {N \choose k} = \frac{N!}{k! (N-k)!}$$
It follows that $$p_{N+1,k} = p_{N,k-1} + p_{N,k} = \frac{N!}{(k-1)! (N-k+1)!} + \frac{N!}{k! (N-k)!} $$ $$= \frac{N! k}{k! (N-k+1)!} + \frac{N!(N-k+1)}{k! (N-k+1)!} $$
$$= \frac{N!(N+1)}{k! (N-k+1)!} = \frac{(N+1)!}{k! (N-k+1)!} = {{N+1} \choose k}$$
Thus, we have proved that the formula is correct for the case $n =N+1$. By mathematical induction principle, we have proved the following general formula for the Pascal's triangle numbers $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
Let us make a remark about the notation ${n \choose k}$. This notation reads "$n$ choose $k$", this is because ${n \choose k}$ is precisely the number of ways to choose $k$ objects (regardless of the ordering) from $n$ given objects. For example, if we are given $4$ fish then there are exactly ${4 \choose 2} = 6$ ways to choose $2$ fish.
 |
| there are exactly ${4 \choose 2} = 6$ ways to choose $2$ fish from $4$ given fish |
We are now using induction to prove the binomial identity $$(x+y)^n = x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$
The identity is clearly correct for the case $n=0$ and the case $n=1$. Suppose that the identity is correct for any $0 \leq n \leq N$, where $N \geq 1$. We will prove the identity is also correct for the case $n=N+1$.
Indeed,
$$(x+y)^{N+1} = (x+y) (x+y)^N $$ $$= (x+y)(x^N + p_{N,1} x^{N-1} y + p_{N,2} x^{N-2} y^2 + \dots + p_{N, N-2} x^{2} y^{N-2} + p_{N,N-1} x y^{N-1} + y^N)$$
$$= x^{N+1} + p_{N,1} x^{N} y + p_{N,2} x^{N-1} y^2 + \dots + p_{N, N-2} x^{3} y^{N-2} + p_{N,N-1} x^2 y^{N-1} + x y^N$$
$$ ~~~~ + x^N y + p_{N,1} x^{N-1} y^2 + p_{N,2} x^{N-2} y^3 + \dots + p_{N, N-2} x^{2} y^{N-1} + p_{N,N-1} x y^{N} + y^{N+1}$$
Based on the rule of the Pascal's triangle then $$p_{N,1} + 1 = p_{N+1,1}, p_{N,2} + p_{N,1} = p_{N+1,2}, \dots, p_{N,N-1} + p_{N, N-2} = p_{N+1, N-1}, 1 + p_{N,N-1} = p_{N+1,N},$$ therefore,
$$(x+y)^{N+1} = x^{N+1} + p_{N+1,1} x^{N} y + p_{N+1,2} x^{N-1} y^2 + \dots + p_{N+1, N-1} x^{2} y^{N-1} + p_{N+1,N} x y^{N} + y^{N+1}$$
Thus, we have proved that the identity is correct for the case $n=N+1$. By mathematical induction principle, we have proved the following binomial identity is correct for any $n$
$$(x+y)^n = x^n + p_{n,1} x^{n-1} y + p_{n,2} x^{n-2} y^2 + \dots + p_{n,n-2} x^{2} y^{n-2} + p_{n,n-1} x y^{n-1} + y^n$$ $$= x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$
Substituting $y$ by $-y$ we obtain the following identity
$$(x-y)^n = x^n - {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 - \dots + (-1)^{n-2}{n \choose {n-2}} x^{2} y^{n-2} + (-1)^{n-1}{n \choose {n-1}} x y^{n-1} + (-1)^n y^n$$
That's all for now. See you again in the next post.
Homework.
1. Prove that if $p$ is a prime number then ${p \choose k}$ is divisible by $p$ for any $0 < k < p$. Thus, obtaining the following modulo equality $$(x+y)^p = x^p + y^p \pmod{p}$$
2. Prove the following equalities
$$1 + {2012 \choose 1} + {2012 \choose 2} + \dots + {2012 \choose 2010} + {2012 \choose 2011} + 1 = 2^{2012}$$
$$1 + {2012 \choose 2} + {2012 \choose 4} + \dots + {2012 \choose 2010} + 1=2^{2011}$$
$${2012 \choose 1} + {2012 \choose 3} + \dots + {2012 \choose 2009} + {2012 \choose 2011} = 2^{2011}$$
3. Use $\Delta$ to denote the following operation $$\Delta p(x) = p(x+1) - p(x)$$
Applying $\Delta$ one more time for $\Delta p(x)$, we have $$\Delta^2 p(x) = \Delta (\Delta p(x)) = (p(x+2) - p(x+1)) - (p(x+1) - p(x)) = p(x+2) - 2 p(x+1) + p(x)$$
Applying $\Delta$ one more time, we have $$\Delta^3 p(x) = p(x+3) - 3p(x+2) + 3 p(x+1) - p(x)$$
State and prove the general formula.