1
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – rah4927 Apr 1 '14 at 7:51
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mikky Davey Apr 1 '14 at 8:33
  • $\begingroup$ 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. $\endgroup$ – drhab Apr 1 '14 at 8:40
2
$\begingroup$

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.

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

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

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

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.