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!
 A: 
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$.
A: We begin with some preliminary theory.
A polynomial in $f(x)$ of degree $n$ can be written in the form
$\tag 1 f(x) = \displaystyle \sum_{u+v=n}c_{(u,v)}x^u \quad \text{ where } c_{(u,0)} \ne 0$
and the ordered pairs $(u,v)$ are in $\Bbb N \times \Bbb N$.
We have the following
$\tag 2 (1+x) f(x) = \displaystyle \sum_{u+v=n+1}c_{(u,v)}x^u \; \text{   where } 
c_{(0,n+1)} = c_{(0,n)} \land c_{(n+1,0)} = c_{(n,0)} \land \big[(u+v= n+1 \land uv \gt 0) \implies c_{(u,v)} = c_{(u-1,v)} + c_{(u,v-1)}\big]$
This is not difficult to understand
(the coefficients are: vertical shifted by $1$ and horizontally shifted by $x$)
or to prove.
Assume we can write as true
$\tag 3
(1 + x)^n = \displaystyle \sum_{u+v=n}c_{(u,v)}x^u \text{ where }  c_{(u,v)} = \binom{n}{u}$ 
Using $\text{(2)}$ and Pascal's rule it is simple to prove that
$\tag 4
(1 + x)^{n+1} = \displaystyle \sum_{u+v=n+1}c_{(u,v)}x^u \text{ where }  c_{(u,v)} = \binom{n+1}{u}$ 
