Mathematical induction for discrete math problem I need to use mathematical induction to prove that
$$(z+1)^n=\sum_{k=0}^n{n\choose k}z^k$$
$z$ is any complex variable
I know that ${n\choose k}=\frac{n!}{k!(n-k)!}$ and that $0!=1!=1$. I did the first step and tested simple numbers and got right answers, then moved to second step where I rewrote it in terms of m as well as m+1 but i am having trouble actually working out the last step where I am adding ${m+1\choose k}z^{m+1}$ to $(z+1)^m$. Any help would be much appreciated. 
 A: You will need to use induction on $n$, as well as Pascal's rule, which states that $${n-1\choose k}+{n-1\choose k-1}={n\choose k}$$
A: Note that the top index
($n$)
of the binomial coefficients
($\binom{n}{k}$)
changes when you go
from $n$ to $n+1$.
That is why you can't just
add one term to the sum - 
all the terms change.
As vadim123 wrote,
you need to use
${n-1\choose k}+{n-1\choose k-1}={n\choose k}
$
to enable the proof by induction
to go through.
Here is the proof
of the induction step.
This is the kind of proof
you will need to both
understand and 
be able to develop.
If
$(1+z)^n
=\sum_{k=0}^n{n\choose k}z^k
$
then
$\begin{array}\\
(1+z)^{n+1}
&=(1+z)(1+z)^{n}
\qquad\text{split out }(1+z)^n \text{ so you can use the induction hypothesis}\\
&=(1+z)\sum_{k=0}^n{n\choose k}z^k
\qquad\text{use the induction hypothesis}\\
&=\sum_{k=0}^n{n\choose k}z^k+z\sum_{k=0}^n{n\choose k}z^k
\qquad\text{use the distributive law}\\
&=\sum_{k=0}^n{n\choose k}z^k+\sum_{k=0}^n{n\choose k}z^{k+1}
\qquad\text{multiply each term in the second sum by }z\\
&=\sum_{k=0}^n{n\choose k}z^k+\sum_{k=1}^{n+1}{n\choose k-1}z^{k}
\qquad\text{make all exponents of }z\text{s }k\\
&={n\choose 0}z^0+\sum_{k=1}^n{n\choose k}z^k+\sum_{k=1}^{n}{n\choose k-1}z^{k}+{n\choose n}z^{n+1}
\qquad\text{get common ranges for both sums}\\
&=1+\sum_{k=1}^n\left({n\choose k}+{n\choose k-1}\right)z^{k}+z^{n+1}
\qquad\text{combine common terms}\\
&=1+\sum_{k=1}^n{n+1\choose k}z^{k}+z^{n+1}
\qquad\text{use formula for binomial coefficients}\\
&=\sum_{k=0}^{n+1}{n+1\choose k}z^{k}
\qquad\text{fold in terms for }z^0 \text{ and } z^{n+1}\\
\end{array}
$
