I'm unsure of how to continue in my proof. How can I prove the follow through induction:
$\sum\limits_{k=66}^n {k-1 \choose 65} = {n \choose 66}$ where $n \geq k \geq 66$
Basis:Let $n=66$.
$$\sum\limits_{k=66}^{66} {66-1 \choose 65} = {66 \choose 66}$$
$$1 = 1$$
The basis holds.
Induction Hypothesis: Suppose $n=m$ holds for all $m\geq 66$
Induction Step: Consider $m+1$.
$$\sum\limits_{k=66}^{m+1} {k-1 \choose 65} = {m+1 \choose 66}$$
Answer
$$\sum\limits_{k=66}^{m+1} {k-1 \choose 65} ={m\choose 65} + \sum\limits_{k=66}^{m} {k-1 \choose 65} \stackrel{\star}{=} {m\choose 65}+{m\choose 66} = {m+1 \choose 66}$$
Where $\star$ holds because the identity holds for $m$
However, there is a little (well, not even) error in your "basis-step". $\sum\limits_{k=66}^{66} {k-1 \choose 65}$ is of course equal to ${65\choose 65}$. Indeed this is the same as ${66\choose 66}$
No comments:
Post a Comment