# Prove Binomial Theory

• December 16th 2009, 03:23 AM
calfever
Prove Binomial Theory
Prove Binomial Theory by Mathematic Induction
Cn,r<(n+1)^r ;0<=r<=n
• December 16th 2009, 03:24 AM
mr fantastic
Quote:

Originally Posted by calfever
Prove Binomial Theory by Mathematic Induction
Cn,r<(n+1)^r ;0<=r<=n

proof binomial theorem induction - Google Search=
• December 16th 2009, 11:02 AM
awkward
Quote:

Originally Posted by calfever
Prove Binomial Theory by Mathematic Induction
Cn,r<(n+1)^r ;0<=r<=n

I think Mr. F has misinterpreted the problem statement due to its misleading title. I think the problem is:

Prove that
$C(n,r) \leq (n+1)^r$ for all $0 \leq r \leq n$ ....(*)
by mathematical induction.
Note that I have changed the less-than in the original statement to less-than-or-equal. Otherwise (*) would be false when r=0.

I'm going to assume you know the important identity $C(n,r-1) + C(n,r) = C(n+1,r)$.

First check the case $n = 0$:
If $n=0$ then the only possible value of r is $r=0$.
$C(0,0) = 1$ and $(0+1)^0 = 1$, so (*) is true.

Now suppose that for some integer k we have
$C(k,r) \leq (k+1)^r$ for all $0 \leq r \leq k$.
I will let you check the case $r=0$.
If $r \neq 0$ then $0 \leq r-1 \leq k$, so by assumption we also have
$C(k,r-1) \leq (k+1)^{r-1}$.

$C(k,r) + C(k,r-1) \leq (k+1)^r + (k+1)^{r-1}$
$C(k+1,r) \leq (k+1)^{r-1} (k + 1 + 1) < (k+2)^{r-1} (k+2) = (k+2)^r$
so (*) holds for $n=k+1$
By mathematical induction, (*) is true for all $n \geq 0$.