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...