1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I understand that. What I didn't understand was how $\ f_{n+4}=(4f_{n+1}-f_{n-2})$. $\endgroup$ – ErinA Feb 25 '18 at 22:42
  • $\begingroup$ @ErinA: exactly for the same reason that $f_{n+5}=(4f_{n+2}-f_{n-1})$. $\endgroup$ – Yves Daoust Feb 25 '18 at 22:44
  • $\begingroup$ 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. $\endgroup$ – ErinA Feb 25 '18 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.