Prove Binomial Theory by Mathematic Induction
Cn,r<(n+1)^r ;0<=r<=n
Use Google.
proof binomial theorem induction - Google Search=
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$.