Prove
\begin{equation*}
(a+b)^n=\sum_{i=0}^{n}\binom{n}{i}a^{n-i}b^i
\end{equation*}
by induction on \(n\text{.}\)
Base step: Let \(n=0\text{.}\) Then
\begin{equation*}
(a+b)^0=1\text{.}
\end{equation*}
Also,
\begin{equation*}
\sum_{i=0}^{0}\binom{0}{i}a^{0-i}b^i=a^0b^0=1.
\end{equation*}
Induction step: Assume
\((a+b)^k=\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\text{.}\)
Show
\((a+b)^{k+1}=\sum_{i=0}^{k+1}\binom{k+1}{i}a^{k+1-i}b^i\)
\begin{align*}
(a+b)^{k+1}&=(a+b)^k(a+b)\\
&=\biggl(\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\biggr)(a+b)\\
&=a\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i+b\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\\
&=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^{i+1}
\end{align*}
Now we want to change the index of the second sum. This is just a substitution of variable that allows us to shift how we index the terms. If we were to write out the sum, rather than have it in summation notation, we would not need this step. But it allows us to easily combine like terms in the two summations. So, in the second sum, let \(j=i+1\text{,}\) so when \(i=0, j=1\text{;}\) when \(i=k, j=k+1\text{,}\) and \(i=j-1\text{.}\) We get
\begin{align*}
(a+b)^{k+1}&=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^{i+1}\\
&=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{j=1}^{k+1}\binom{k}{j-1}a^{k+1-j}b^j\\
&=a^{k+1}+\sum_{i=1}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{j=1}^{k}\binom{k}{j-1}a^{k+1-j}b^j+b^{k+1}\\
&\text{where we pulled out the first term of the first sum}\\
&\text{and the last term of the second sum}\\
&=a^{k+1}+\sum_{i=1}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=1}^{k}\binom{k}{i-1}a^{k+1-i}b^i+b^{k+1}\\
&\text{where we just relabeled the index in the second sum}\\
&=a^{k+1}+\sum_{i=1}^{k}\biggl[\binom{k}{i}+\binom{k}{i-1}\biggr]a^{k+1-i}b^i+b^{k+1}\\
&\text{where we combined like terms in the two sums}\\
&=a^{k+1}+\sum_{i=1}^{k}\binom{k+1}{i}a^{k+1-i}b^i+b^{k+1}\\
&\text{by Pascal's Formula}\\
&=\sum_{i=0}^{k+1}\binom{k+1}{i}a^{k+1-i}b^i
\end{align*}
