induction with a binomial

**dwsmith** · June 21st 2011, 07:31 PM

Prove $\forall n\geq 0$

$\binom{n}{0}+\binom{n}{1}+\cdots +\binom{n}{n}=2^n$

$p(0): \ \binom{n}{0}=1=2^0=1$

Assume p(k) is true

$p(k): \ \binom{k}{0}+\binom{k}{1}+\cdots +\binom{k}{k}=2^k$

Prove

$p(k+1): \ \binom{k}{0}+\binom{k}{1}+\cdots +\binom{k+1}{k+1}=2^{k+1}$

Simply adding the next binomial term to both sides doesn't help. Any ideas?

**TKHunny** · June 21st 2011, 08:09 PM

You're a few "k+1"s short - actually, k of them.

$2^{k+1} - 2^{k} = 2^{k}\cdot(2-1) = 2^{k}$

Focus on the 3rd term (2 in the bottom of the choose) and see if it makes any sense.

**pickslides** · June 21st 2011, 08:22 PM

Hi dw, it might help if,

$p(k+1): \ \binom{k+1}{0}+\binom{k+1}{1}+\cdots +\binom{k+1}{k+1}=2^{k+1}$

Thread: induction with a binomial

LinkBack

Thread Tools

Display

induction with a binomial

Re: induction with a binomial

Re: induction with a binomial

Similar Math Help Forum Discussions

Combining Multiple Binomial (or Negative Binomial) Distributions

Sums of Binomial Coefficients - proof by induction

[SOLVED] Y binomial r.v, show that the distribution of n-y is binomial r.v

Difference between binomial and negative binomial distribution

Relation between Negative Binomial and Binomial Distros