proof by induction: sum of binomial coefficients $\sum_{k=0}^n (^n_k) = 2^n$ [duplicate]

For $n\in\mathbb{Z}_{\geq 0}$ and $k\in\mathbb{Z}$ define $\binom{n}{k}$ together with the convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,\dots,n\right\} $.

If $n>0$ then for every $k\in\mathbb{Z}$: $$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$$

To be shown is that $\sum_{k\in\mathbb{Z}}\binom{n}{k}=2^n$ for each nonnegative integer $n$. The base case $n=0$ is obvious.

Let it be that $n>0$ and that the statement is true for $n-1$. Then:

$\sum_{k\in\mathbb{Z}}\binom{n}{k}=\sum_{k\in\mathbb{Z}}\left[\binom{n-1}{k-1}+\binom{n-1}{k}\right]=\sum_{k\in\mathbb{Z}}\binom{n-1}{k-1}+\sum_{k\in\mathbb{Z}}\binom{n-1}{k}=2^{n-1}+2^{n-1}=2^{n}$

showing that the statement is also true for $n$.

By induction it has now been shown that $\sum_{k\in\mathbb{Z}}\binom{n}{k}=2^n$ for each nonnegative integer $n$.

Think of $(1+1)^n=....$ equal the sum of the coefficients .

EDIT: This is not a good recipe for induction , but hopefully it gives some insight into the problem, and , I hope, a nice, direct alternative proof.

This is a special case of the binomial theorem: http://en.wikipedia.org/wiki/Binomial_theorem. To prove this by induction you need another result, namely $$ \binom{n}{k}+\binom{n}{k-1} = \binom{n+1}{k}, $$ which you can also prove by induction.

Note that an intuitive proof is that your sum represents all possible ways to pick elements from a set of $n$ elements, and thus it is the amount of subsets of a set on $n$ elements. To form a subset you must decide for each element whether to include it or not, which gives 2 different sets. Thus the total is then $2^n$.

First note that the sum of the coefficients in $(x+y)^n$ is just the value obtained by setting $x=1$ and $y=1$; I'm sure you know how to compute $(1+1)^n$ directly.

So now you know why the result is true, how do you get a proof by induction on$~n$? Well observe that for $n>0$ the expression $(x+y)^n$ is just short for $(x+y)^{n-1}(x+y)$. So every coefficient in $(x+y)^{n-1}$ contributes twice to a coefficient in $(x+y)^n$, once by multiplying its term by $x$, and another time by multiplying its term by $y$. If you identify which term thus contributes to which two other terms (this is easy) you will find a relation between binomial coefficients in rows $n-1$ and $n$ of Pascal's triangle, which is known as Pascal's recurrence. Using it you can easily see why the sum of the entries in row$~n$ is twice that of the entries in row$~n-1$. If you think of it, it is an immediate consequence of the fact that each coefficient in row$~n-1$ contributes twice to a coefficient in row$~n$, even without figuring out exactly to which coefficients it contributes (though you will that for a proper formal induction proof).