**Solution to Abstract Algebra by Dummit & Foote 3rd edition Chapter 7.3 Exercise 7.3.25**

Solution: We begin with some lemmas.

Recall that ${n \choose k} = \frac{n!}{k!(n-k)!}$, where $n$ is a natural number and $0 \leq k < n$.

Lemma: Let $n$ be a natural number and $0 \leq k < n$. Then the following hold.

(1) ${n \choose 0} = {n \choose n} = 1$.

(2) ${{n+1} \choose {k+1}} = {n \choose k} + {n \choose {k+1}}$.

Proof: The first facts follow directly from the definition of $n \choose k$. For the second, note the following.

\begin{align*}\displaystyle\binom{n}{k+1} + \displaystyle\binom{n}{k} =&\ \dfrac{n!}{(k+1)!(n-(k+1))!} + \dfrac{n!}{k!(n-k)!}\\

=&\ \dfrac{n!(n-k)}{(k+1)!(n-k)!} + \dfrac{n!(k+1)}{(k+1)!(n-k)!}\\

=&\ \dfrac{(n+1)!}{(k+1)!((n+1)-(k+1))!}\\

=&\ \displaystyle\binom{n+1}{k+1}.\square\end{align*} We now prove the main result. Let $a,b \in R$. We proceed by induction on $n$; in a ring with 1, we use the convention that $x^0 = 1$. Then for the base case, we have $(a+b)^0 = 1 = \binom{0}{0} a^0b^0$.

For the inductive step, suppose $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}.$$ Then we have the following.\begin{align*}(a+b)^{n+1} =&\ (a+b)(a+b)^n\\

=&\ (a+b)\left[ \displaystyle\sum_{k=0}^n \displaystyle\binom{n}{k} a^k b^{n-k} \right]\\

=&\ \left[ \displaystyle\sum_{k=0}^n \displaystyle\binom{n}{k} a^{k+1} b^{n-k} \right] + \left[ \displaystyle\sum_{k=0}^n \displaystyle\binom{n}{k} a^kb^{n-k+1} \right]\\

=&\ a^{n+1} + \left[ \displaystyle\sum_{k=0}^{n-1} \displaystyle\binom{n}{k} a^{k+1} b^{n-k} \right] + \left[ \displaystyle\sum_{k=1}^n \displaystyle\binom{n}{k} a^kb^{n-k+1} \right] + b^{n+1}\\

=&\ a^{n+1} + \left[ \displaystyle\sum_{k=1}^n \displaystyle\binom{n}{k-1} a^{k} b^{n-k+1} \right] + \left[ \displaystyle\sum_{k=1}^n \displaystyle\binom{n}{k} a^kb^{n-k+1} \right] + b^{n+1}\\

=&\ a^{n+1} + \left[ \displaystyle\sum_{k=1}^n \left[ \displaystyle\binom{n}{k-1} + \displaystyle\binom{n}{k} \right] a^kb^{(n+1)-k} \right] + b^{n+1}\\

=&\ \displaystyle\binom{n+1}{n+1} a^{n+1}b^{(n+1)-(n+1)} + \left[ \displaystyle\sum_{k=1}^n \displaystyle\binom{n+1}{k} a^kb^{(n+1)-k} \right] + \displaystyle\binom{n+1}{0}a^0b^{(n+1)-0}\\

=&\ \displaystyle\sum_{k=0}^{n+1} \displaystyle\binom{n+1}{k} a^k b^{(n+1)-k}.\end{align*}Thus the result holds for all natural numbers $n$.