Saturday, December 17, 2016

proof verification - Proving that $f_2+f_4+cdots+f_{2n}=f_{2n+1}-1$ for Fibonacci numbers by induction





Given: $f_1 = f_2 = 1$ and for $n \in\mathbb{N}$, $f_{n+2} =f_{n+1} + f_n$.



Prove that $f_2 + f_4 + \dots + f_{2n} = f_{2n+1}- 1$.




Would you start with setting $f_2 + f_4 + \dots + f_{2n}= a_n$?



Then for the base case let $a_1=1$ LHS$=1$ and RHS$=2-1=1$ so base case holds.



Then the inductive hypothesis: Assume $f_2 + f_4 + \dots + f_{2n} = f_{2n+1}- 1$




$\textbf{NTS}$: $f_2 + f_4 + \dots + f_{2n} +f_{2n+2} = f_{2n+3}- 1$



Inductive step: By inductive hypothesis $f_2 + f_4 + \dots + f_{2n}=f_{2n+1}- 1$



So $f_{2n+1}- 1+f_{2n+1}$=$f_{2n+2}- 1$. 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

$$
f_2 + f_4 + \cdots + f_{2n}+\color{red}{f_{2n+2}}=\color{red}{f_{2n+3}}- 1,
$$ then using the inductive hypothesis, we have to prove that
$$
f_{2n+1}-1+\color{red}{f_{2n+2}}=\color{red}{f_{2n+3}}- 1.
$$ Can you take it from here?


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