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