proof by induction: sum of binomial coefficients $\sum_{k=0}^n (^n_k) = 2^n$ Question:
Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. 
i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$
i.e. prove $$\sum_{k=0}^n \binom nk = 2^n.$$ Hint: use induction and use Pascal's identity
What I have so far:
$$p(n)= \sum^{n}_{k=0}{n\choose k} = 2^n$$
$$P(0)=\sum^{0}_{k=0}{0\choose k} = 2^0$$
LHS: ${0\choose k}=1$ RHS $2^0=1$
now of for the inductive step I am getting all tangled up in my terms. It seems like a silly thing to get confused on but every inductive proof I've done I do $P(n) =$ something to $P(1)$ then my inductive step is $P(k)$ and $P(k+1)$ but I don't think can use that terminology because those variables are in the problem. Also the two (i.e) are throwing me off, am i even setting it up right to begin with or am I missing something. How does $(x+y)^n$ even fit in to here, I know how it connects to pascals because I googled it but I don't understand how it fits into my inductive proof.
I need help getting on track form here. PS my professor is a stickler for set up so making sure I write it properly is a big part of it.
 A: 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$.
A: 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.
A: 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$.
A: 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).
