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

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

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$.

Answer 4

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).