Saturday, December 17, 2016

proof verification - Proving that f2+f4+cdots+f2n=f2n+11 for Fibonacci numbers by induction





Given: f1=f2=1 and for nN, fn+2=fn+1+fn.



Prove that f2+f4++f2n=f2n+11.




Would you start with setting f2+f4++f2n=an?



Then for the base case let a1=1 LHS=1 and RHS=21=1 so base case holds.



Then the inductive hypothesis: Assume f2+f4++f2n=f2n+11




NTS: f2+f4++f2n+f2n+2=f2n+31



Inductive step: By inductive hypothesis f2+f4++f2n=f2n+11



So f2n+11+f2n+1=f2n+21. As was to be shown.



Is this correct or did I need to show more algebra in my inductive step ?


Answer



Hint. The inductive step is rather

f2+f4++f2n+f2n+2=f2n+31,

then using the inductive hypothesis, we have to prove that
f2n+11+f2n+2=f2n+31.
Can you take it from here?


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...