# Thread: 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 $\displaystyle F_n$...Fibonacci sequence or what!?

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

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

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

$\displaystyle 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 $\displaystyle F_n$...Fibonacci sequence or what!?

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

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

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

$\displaystyle 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 $\displaystyle 5F_{n-5}+3F_{n-6}$? would it not be $\displaystyle 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 $\displaystyle 5F_{n-5}+3F_{n-6}$? would it not be $\displaystyle 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.