Prove that the polynomial relationship $$(1+x)^n=\sum_{k=0}^n {n \choose k} x^k$$ holds for all positive integers $n$.
I'm trying to use proof by induction, the base case is pretty simple, but I'm having difficulty working around the summation.
I want to substitute $m+1$ in for m which gives me $$(1+x)^{n+1}=\sum_{k=0}^{n+1} {n+1 \choose k} x^k,$$ and I know I want to break up the right hand side into $(1+x)^n\cdot(1+x)$, but the LHS has me confused.
What is the process like when working with summations in proof by inductions?
You want to break up the left-hand side, in order to use the induction hypothesis: \begin{align} (1+x)^{n+1} &=(1+x)(1+x)^n \\[6px] &=(1+x)\sum_{k=0}^n\binom{n}{k}x^k &&\text{(induction hypothesis)} \\[6px] &=\sum_{k=0}^n\binom{n}{k}x^k+\sum_{k=0}^n\binom{n}{k}x^{k+1} &&\text{(distributive property)} \\[6px] &= 1+\sum_{k=1}^n\binom{n}{k}x^k+\sum_{k=0}^{n-1}\binom{n}{k}x^{k+1}+x^{n+1} \\[6px] &= 1+\sum_{k=1}^n\binom{n}{k}x^k+\sum_{k=1}^{n}\binom{n}{k-1}x^k+x^{n+1} &&\text{(index shifting)} \\[6px] &= 1+\sum_{k=1}^n\left(\binom{n}{k}+\binom{n}{k-1}\right)x^k+x^{n+1} \end{align} Now recognize a know identity and finish up.