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

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.

## marked as duplicate by Martin Sleziak, zhoraster, JonMark Perry, Claude Leibovici, LutzLNov 18 '16 at 12:28

• Since you want an inductive proof,I will give you some ways to come up with one.First,experiment with any nth and (n+1)th row of Pascal's triangle.Note that the (n+1)th row can be written as a sum of two entries of the nth row.Then conclude. – rah4927 Apr 1 '14 at 7:51

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

• ok so to set this up for a proper formal inductive proof I would make my base case n=1 and my inductive case what n=? I'm sorry if I seem to be talking in circles but I understand why it works i just can't seem to turn it into a formal proof by induction – Mikky Davey Apr 1 '14 at 8:33
• You can do it with base $n=0$. We have $\binom{0}{0}:=1=2^{0}$. Then you take a positive integer $n$ and - as pointed out in my answer - you find that the statement - if it is true for $n-1$ - is true for $n$. That completes your proof by induction. – drhab Apr 1 '14 at 8:40

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.

• OP is after a proof by induction; this does not obviously lead to one. – Marc van Leeuwen Apr 1 '14 at 7:45
• @Marc van Leeuwen: O.K, I edited to make that point; hopefully this will be a good complement to an induction argument. – user99680 Apr 1 '14 at 7:48

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

• ok that makes sense (this coming from the first i.e. correct?) but how would I set up my inductive proof then? – Mikky Davey Apr 1 '14 at 8:02
• Have a look at the link, they give a general outline there;) – Marc Apr 1 '14 at 9:39

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