Using Complete Induction to Prove Fibonacci Numbers

Question

Use PCI (Principle of Complete Induction) to prove the $\ f_{n+6}=4f_{n+3}+f_n$ for all natural numbers $n$.

Induction Step:

Let $S$ be the set of natural numbers and let $\ m \in \mathbb{N}$ and {$1, 2, 3,..., m-1$} $\subseteq S$

By the Fibonacci definition:

$$f_{m+6}=f_{m+5}+f_{m+4}......(1)$$

$$f_{m+6}= (4f_{m+2}+f_{m-1})+f_{m+4}......(2)$$

$$f_{m+6}= 4(f_{m+3}-f_{m-1})+f_{m-1} +f_{m+4}......(3)$$

$$f_{m+6}= 4f_{m+3}-4f_{m-1}+f_{m-1} +(4f_{m+1}+f_{m-2})......(4)$$

$$f_{m+6}= 4f_{m+3}+(f_{m-1} +f_{m-2})......(5)$$

$$ f_{m+6}=4f_{m+3}+f_m$$

---

This was the answer but I'm having a little trouble understanding it. I figured out the hypothesis $n=1$ so I didn't include it. What I don't understand is line 2 and line 4.

By line 2, $\ f_{m+5}$ is broken down to $(4f_{m+2}+f_{m-1})$. I assumed this was because $\ f_{m+6}+f_{m-1}=f_{m+5}$

But in line 4, $\ f_{m+4}$ is broken down into $\ (4f_{m+1}+f_{m-2})$. When I apply the same method as before, I don't get $\ f_{m+4}$. Can someone explain to me how this is done?

Answer 1

The induction step is

$$f_{n+6}=f_{n+5}+f_{n+4}=(4f_{n+2}-f_{n-1})+(4f_{n+1}-f_{n-2})=(4f_{n+2}+4f_{n+1})-(f_{n-1}+f_{n-2})=4f_{n+3}-f_n.$$

[In fact, this works with any linear combination of the numbers.]

So the complete proof rests on the base case(s).