Proving an identity of Fibonacci Numbers by induction

Question

Say we know this as a given:

$$E_0 = A$$ $$E_1 = B$$ $$E_2 = A + B$$ $$E_3 = A + 2B$$ $$E_4 = 2A + 3B$$ $$E_5 = 3A + 5B$$

$E_{n+1}$ is defined as: $$E_{n+1} = E_n + E_{n-1}$$

You can start to see the Fibonacci numbers coming through. I need to prove that $$E_n = F_{n-1}A + F_nB$$

My text says this is easy to prove by induction on $n$, but I'm having trouble with it. Here is what I have:

Base Case: $n = 1$ $$E_1 = F_0A + F_1B = 0A + 1B$$ $$E_1 = B.$$ Good so far. Now assume true for $n=k$: $$E_k = F_{k-1}A + F_kB$$

This is where I'm stuck. All other induction problems I have done have some sort of instance like $1 + 2 + ... + k$ so I could use $n = k + 1$ for my next case. However, I don't really see that pattern happening here. Maybe I have been looking at it for too long.

Where do I go from here?

Answer 1

We know that

$${F_{k + 1}} = {F_k} + {F_{k - 1}}$$

Now we should make use of it. Suppose the claim is true for $n=k$ and $n=k-1$. Then we have

$$\eqalign{ & {E_{k + 1}} = {E_k} + {E_{k - 1}} = \left( {{F_{k - 1}}A + {F_k}B} \right) + \left( {{F_{k - 2}}A + {F_{k - 1}}B} \right) \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \left( {{F_{k - 1}} + {F_{k - 2}}} \right)A + \left( {{F_k} + {F_{k - 1}}} \right)B \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = {F_k}A + {F_{k + 1}}B \cr} $$

That's all.

Answer 2

We have $$ E_k = E_{k-1} + E_{k-2}\\ = F_{k-2}A + F_{k-1}B + F_{k-3}A + F_{k-2}B $$ by the induction hypothesis. We rearrange this into $$ (F_{k-2} + F_{k-3})A + (F_{k-1} + F_{k-2})B $$ and then apply the Fibonacci recursion inside each parenthesis to get $$ F_{k-1}A + F_kB $$ which is what we wanted.