Solving binomial theorem via induction I'm trying to prove binomial theorem by induction, but I'm a little stuck. I would look at online resources as this problem has been done many times, but the version I am trying to prove the binomial theorem in a different form.
$$(1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$$
I'm mostly confused as to how I can make the left side be equivalent to a summation, any help is appreciated. Try to hint me along!


We show by induction the following is valid for $n\geq 0$
  \begin{align*}
(1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k
\end{align*}

Base step: $n=0$

We have to show
  \begin{align*}
(1 + x)^0 = \sum_{k = 0}^{0} \binom{0}{k} x^k
\end{align*}
Since the left-hand side is $$(1+x)^0=1$$
  and the right-hand side is $$\sum_{k = 0}^{0} \binom{0}{k} x^k=\binom{0}{0}x^0=1,$$ both sides are equal and the claim is valid for $n=0$.

Induction hypothesis: $n=N$

We assume the validity of
  \begin{align*}
(1 + x)^N = \sum_{k = 0}^{N} \binom{N}{k} x^k\tag{1}
\end{align*}

Induction step: $n=N+1$

We have to show
  \begin{align*}
(1 + x)^{N+1} = \sum_{k = 0}^{N+1} \binom{N+1}{k} x^k
\end{align*}
We obtain
  \begin{align*}
(1 + x)^{N+1} &= (1+x)(1+x)^N\tag{2}\\
&=(1+x)\sum_{k = 0}^{N} \binom{N}{k} x^k\tag{3}\\
&=\sum_{k = 0}^{N} \binom{N}{k} x^k+\sum_{k = 0}^{N} \binom{N}{k} x^{k+1}\tag{4}\\
&=\binom{N}{0}x^0+\sum_{k=1}^N\binom{N}{k}x^k+\sum_{k=0}^{N-1}\binom{N}{k}x^{k+1}+\binom{N}{N}x^{N+1}\tag{5}\\
&=\binom{N+1}{0}x^0+\sum_{k=1}^N\binom{N}{k}x^k+\sum_{k=1}^{N}\binom{N}{k-1}x^{k}+\binom{N+1}{N+1}x^{N+1}\tag{6}\\
&=\sum_{k=0}^{N+1}\binom{N+1}{k}x^k\tag{7}
\end{align*}
  and the claim follows.

Comment:


*

*In (2) we split the product, since we want to apply the induction hypothesis.

*In (3) we apply the induction hypothesis (1).

*In (4) we multiply out.

*In (5) we separate the first summand $\binom{N}{0}$ from the left sum and the last summand $\binom{N}{N}x^{N+1}$ from the right sum.

*In (6) we use the binomial identities 
\begin{align*}
\binom{N}{0}=\binom{N+1}{0}=1\qquad\text{and}\qquad\binom{N}{N}=\binom{N+1}{N+1}=1
\end{align*}
We also shift the index $k$ of the right sum by one to start from $k=1$. This all is a preparation for the next step to easily collect all the terms in one sum.

*In (7) we apply the binomial identity
\begin{align*}
\binom{N}{k}+\binom{N}{k-1}=\binom{N+1}{k}
\end{align*}
and the two sums can be merged into one sum. We also see the left-most term $\binom{N+1}{0}$ and the right-most term $\binom{N+1}{N+1}$ can be made part of the sum using index $k=0$ and $k=N+1$.
