# Math Help - Proof using Strong Mathematical Induction

1. ## Proof using Strong Mathematical Induction

I would greatly appreciate some direction or hints to finish this problem.

Let n be a natural number such that n>5. Show that Fn=5Fn-4+3Fn-5. (Where all n, n-4, and n-5 are subscripts of F)

I know I need to proceed by way of strong mathematical induction.

Base Case: Suppose n=6. Then, F(6)=5F(6-4)+3F(6-5)= 5F(2)+3F(1).

Now I'm stuck. I'm not even sure how to establish the base case. I realize typically you just show that the statement is true for a variable. However, I don't know how to show the equivalency here. Should I set the Fn equal to a value?

I appreciate any help.!

2. Originally Posted by mathmajor2010
I would greatly appreciate some direction or hints to finish this problem.

Let n be a natural number such that n>5. Show that Fn=5Fn-4+3Fn-5. (Where all n, n-4, and n-5 are subscripts of F)

I know I need to proceed by way of strong mathematical induction.

Base Case: Suppose n=6. Then, F(6)=5F(6-4)+3F(6-5)= 5F(2)+3F(1).

Now I'm stuck. I'm not even sure how to establish the base case. I realize typically you just show that the statement is true for a variable. However, I don't know how to show the equivalency here. Should I set the Fn equal to a value?

I appreciate any help.!

It'd be a great idea if you didn't assume everybody understands your notation and define what os $F_n$...Fibonacci sequence or what!?

And use parentheses: you actually meant $F_n=5F_{n-4}+3F_{n-5}$ , so if your Fibonacci sequence is

$1,1,2,3,5,8,13,21,34, 55,...$, then $F_6=8=5F_2+3F_1=5\cdot 1+3\cdot 1$ and you have the base case.

Suppose truthness for $k , and take $F_{n+1}:=F_n+F_{n-1}$ . The inductive hypotheses tells us that both terms in the RHS fulfill the equality, so:

$F_{n+1}=F_n+F_{n-1}=5F_{n-4}+3F_{n-5}+5F_{n-5}+3F_{n-6}$ ...and now just rearrange these terms and use the definition of Fibonacci sequence...

3. Originally Posted by tonio
It'd be a great idea if you didn't assume everybody understands your notation and define what os $F_n$...Fibonacci sequence or what!?

And use parentheses: you actually meant $F_n=5F_{n-4}+3F_{n-5}$ , so if your Fibonacci sequence is

$1,1,2,3,5,8,13,21,34, 55,...$, then $F_6=8=5F_2+3F_1=5\cdot 1+3\cdot 1$ and you have the base case.

Suppose truthness for $k , and take $F_{n+1}:=F_n+F_{n-1}$ . The inductive hypotheses tells us that both terms in the RHS fulfill the equality, so:

$F_{n+1}=F_n+F_{n-1}=5F_{n-4}+3F_{n-5}+5F_{n-5}+3F_{n-6}$ ...and now just rearrange these terms and use the definition of Fibonacci sequence...
I'm very sorry for the misunderstanding. Hopefully this will be better.

How did you get the addition $5F_{n-5}+3F_{n-6}$? would it not be $F5_{n-3}+3F_{n-4}$?

4. Originally Posted by mathmajor2010
I'm very sorry for the misunderstanding. Hopefully this will be better.

How did you get the addition $5F_{n-5}+3F_{n-6}$? would it not be $F5_{n-3}+3F_{n-4}$?

Just input n-1 instead n in the formula...and be very careful with minus signs!

Tonio

5. In fact, the proof can be derived without using induction at all. Just sum up two consecutive Fibonacci numbers whenever they occur.