the induction step for proving the binomial theorem.

Question

$$\sum_{k=0}^n {n \choose k} x^{n+1-k}y^k+\sum_{k=1}^{n+1} {n \choose k-1}x^{n+1-k}y^k$$

i would like to know how to add the two summations above together including a explanation of how the limits of the two sums will change.

Answer 1

The inductive step involves Pascal's Identity, which is: ${n\choose{k}}+{n\choose{k+1}}={{n+1}\choose{k+1}}$

I will start from the assumption that $(a+b)^n=\sum_{r=0}^{n} {n\choose r}a^{n-r}b^r$

Therefore: $(a+b)^{n+1}=(a+b)^n \cdot (a+b)$

$=\sum_{r=0}^{n} {n\choose r}a^{n-r}b^r \cdot (a+b)$ (using assumption)

$=\{{n\choose0}a^nb^0+{n\choose1}a^{n-1}b^1+....+{n\choose{n-1}}a^1b^{n-1}+{n\choose n}a^0b^n \} \cdot (a+b)$

$=a\cdot{\{{n\choose0}a^nb^0+{n\choose1}a^{n-1}b^1+....+{n\choose{n-1}}a^1b^{n-1}+{n\choose n}a^0b^n \}} + b\cdot{\{{n\choose0}a^nb^0+....++{n\choose n}a^0b^n \}}$

$={\{{n\choose0}a^{n+1}b^0+{n\choose1}a^{n}b^1+....++{n\choose n}a^1b^n \}}+{\{{n\choose0}a^nb^1+{n\choose1}a^{n-1}b^2....++{n\choose n}a^0b^n \}}$

(combine like terms)

$={n\choose0}a^{n+1}b^0+\{{n\choose1}+{n\choose0}\}a^{n}b^1+\{{n\choose2}+{n\choose1}\}a^{n-1}b^2+\{{n\choose3}+{n\choose2}\}a^{n-2}b^3+...+ \{{n\choose{n-1}}+{n\choose{n}}\}a^1b^{n}+{n\choose n}a^0 b^{n+1}$

$={n+1\choose0}a^{n+1}b^0+{n+1\choose1}a^{n}b^1+....+{n+1\choose{n}}a^1b^{n} + {n+1\choose n+1}a^0b^{n+1} $ (using Pascal's Identity)

$=\sum_{r=0}^{n+1} {n+1\choose r}a^{n+1-r}b^r$

Answer 2

I think what you mean is the crucial 'trick' in the inductive step that allows you to sum the factorials:

$$\left(\frac{k}{r-1}\right)+\left(\frac{k}{r}\right)=\left(\frac{k+1}{r}\right) \;\;\;\;\;\;\;(*)$$

Am I right? If not do let me know! Here's why $(*)$ is true:

$$\begin{align}\left(\frac{k}{r-1}\right)+\left(\frac{k}{r}\right)&=\frac{k!}{(r-1)!(k-r+1)!}+\frac{k!}{k!(k-r)!}\\ &=\frac{rk!+(k-r+1)k!}{r!(k-r+1)!}\;\;\;(**)\\&=\frac{(k+1)k!}{r!(k+1-r)!}\\ &=\left(\frac{k+1}{r}\right)\end{align}$$

All we did was put the two factorials on the left onto the same denominator in (**). Is that what you need? Cheers!