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