Friday 11 August 2017

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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...