1. **Problem statement:** Show that $\binom{n}{r} + \binom{n}{r - 1} = \binom{n + 1}{r}$ and prove by induction the binomial theorem expansion: $$ (1 + x)^n = 1 + nx + \dots + \binom{n}{r} x^r + \dots + x^n $$ where $\binom{n}{r} = \frac{n!}{(n-r)! r!}$ and $1 \le r \le n$. --- 2. **Proof of the identity $\binom{n}{r} + \binom{n}{r - 1} = \binom{n + 1}{r}$:** - Start with the right-hand side: $$\binom{n + 1}{r} = \frac{(n+1)!}{r! (n+1 - r)!} = \frac{(n+1)!}{r! (n+1-r)!}$$ - Rewrite as: $$= \frac{(n+1) n!}{r! (n + 1 - r)!}$$ - Express $\binom{n}{r}$ and $\binom{n}{r-1}$: $$\binom{n}{r} = \frac{n!}{r! (n-r)!}, \quad \binom{n}{r-1} = \frac{n!}{(r-1)! (n - (r-1))!} = \frac{n!}{(r-1)! (n - r + 1)!}$$ - Sum left-hand side: $$\binom{n}{r} + \binom{n}{r - 1} = \frac{n!}{r! (n-r)!} + \frac{n!}{(r-1)! (n-r+1)!}$$ - Get common denominator $r! (n-r+1)!$: $$= \frac{n! (n-r+1)}{r! (n-r+1)!} + \frac{n! r}{r! (n-r+1)!} = \frac{n! ((n-r+1) + r)}{r! (n-r+1)!} = \frac{n! (n+1)}{r! (n-r+1)!}$$ - This matches the right-hand side expression for $\binom{n+1}{r}$; hence, $$\binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r}$$ --- 3. **Inductive proof of the binomial theorem:** - **Base case ($n=1$):** $$ (1+x)^1 = 1 + x $$ which matches the theorem. - **Inductive hypothesis:** Assume true for some $n$, i.e., $$ (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k $$ - **Inductive step:** Show for $n+1$: $$ (1+x)^{n+1} = (1+x)(1+x)^n = (1+x) \sum_{k=0}^n \binom{n}{k} x^k = \sum_{k=0}^n \binom{n}{k} x^k + \sum_{k=0}^n \binom{n}{k} x^{k+1} $$ - Shift index in second sum: $$ = \binom{n}{0} + \sum_{k=1}^n \binom{n}{k} x^k + \sum_{k=1}^{n+1} \binom{n}{k-1} x^k $$ - Combine sums for powers $1$ through $n$: $$ = 1 + \sum_{k=1}^n \left[ \binom{n}{k} + \binom{n}{k-1} \right] x^k + \binom{n}{n} x^{n+1} $$ - Using identity from step 2: $$ = 1 + \sum_{k=1}^n \binom{n+1}{k} x^k + x^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} x^k $$ - Hence proved by induction that: $$ (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k $$ --- **Final answers:** 1. $\binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r}$ 2. Binomial theorem proven by induction: $$ (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k $$