Prove Binomial Theory by Mathematic Induction

Cn,r<(n+1)^r ;0<=r<=n

Printable View

- Dec 16th 2009, 03:23 AMcalfeverProve Binomial Theory
Prove Binomial Theory by Mathematic Induction

Cn,r<(n+1)^r ;0<=r<=n - Dec 16th 2009, 03:24 AMmr fantastic
Use Google.

proof binomial theorem induction - Google Search= - Dec 16th 2009, 11:02 AMawkward
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}$.

Adding the two inequalities,

$\displaystyle C(k,r) + C(k,r-1) \leq (k+1)^r + (k+1)^{r-1}$

so by the identity stated above,

$\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$. - Dec 16th 2009, 01:59 PMcalfever
thanks a lot!! AWKWARD