# Using Complete Induction to Prove Fibonacci Numbers

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?

$$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.$$
• I understand that. What I didn't understand was how $\ f_{n+4}=(4f_{n+1}-f_{n-2})$. – ErinA Feb 25 '18 at 22:42
• @ErinA: exactly for the same reason that $f_{n+5}=(4f_{n+2}-f_{n-1})$. – Yves Daoust Feb 25 '18 at 22:44
• I thought $\ (4f_{n+2}-f_{n-1})= f_{n+5}$ because the 4 was added to $\ f_{n+2}$ to make it $\ f_{n+6}-f_{n-1}$ which would equal $\ f_{n+5}$ when added. But when I apply that same method to $\ f_{n+4}=(4f_{n+1}-f_{n-2})$, I get $\ f_{n+5}+f_{n-2}$ which equals $\ f_{n+3}$ when added. – ErinA Feb 25 '18 at 22:54