1

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}$$

GivenPie
  • 479
  • The basis holds, so then show that ${n+1 \choose 66} - {n \choose 66} = {n \choose 65}$. – MT_ Jan 26 '14 at 23:37

1 Answers1

1

$$\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}$

user127.0.0.1
  • 7,267