Proof on Fibonacci sequence: $F(1) + F(3) + \cdots + F(2n-1) = F(2n)$ using induction and recursion

Question

The problem is:

Use induction and the recursive formula to prove that: $$F(1) + F(3) + \cdots + F(2n-1) = F(2n)$$

For the base case I let $n=1$ which gave $$F(1) = F(2(1))$$

$$1=1$$

Which is true.

Then I assumed for $n=n-1$ and subbed that into the original given function:

$$F(1) + F(3) + \cdots + F(2(n-1)-1) = F(2(n-1))$$

$$F(1) + F(3) + \cdots + F(2n -3) = F(2(n-1))$$

Then, I added $F(n-1)$ to both sides of the original function to try and get that to equal $F(2(n-1))$ which would prove what I was trying to prove. (Or so I thought) This gives me:

$$F(1) + F(3) + \cdots + F(2(n-1)) + F(n-1) = F(2n) + F(n-1)$$

Which I have expanded out a number of ways, none of which give me the answer I am looking for.

I'm not 100% sure that adding $F(n-1)$ to both sides is the correct 3rd step, I used the same method from a different example proof but that didn't involve Fib numbers. Any help would be appreciated.

Answer 1

You're almost there. You have $$F(1) + F(3) + ... + F(2n -3) = F(2(n-1))$$ by induction. Now add $F(2n-1)$ to both sides so that the LHS is in the form you want, giving $$F(1) + F(3) + ... + F(2n -3) +F(2n-1)= F(2(n-1)) + F(2n-1) = F(2n-2)+F(2n-1) = F(2n)$$.

Answer 2

Hint: If we know $F(1) + F(3) + \dots + F(2n-1) = F(2n)$, then we can write $$F(1) + F(3) + \dots + F(2n-1) + F(2n+1) = F(2n) + F(2n+1) = ?$$

Answer 3

Inductionstep: $F_{2n+2}=F_{2n}+F_{2n+1}\stackrel{\text{indhyp}}{=}F_{1}+F_{3}+\cdots+F_{2n-1}+F_{2n+1}$