Friday, April 6, 2018

Proving Summations




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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...