Prove Binomial Theory

• Dec 16th 2009, 03:23 AM
calfever
Prove Binomial Theory
Prove Binomial Theory by Mathematic Induction
Cn,r<(n+1)^r ;0<=r<=n
• Dec 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=
• Dec 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
$\displaystyle C(n,r) \leq (n+1)^r$ for all $\displaystyle 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 $\displaystyle C(n,r-1) + C(n,r) = C(n+1,r)$.

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

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

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