• Support PF! Buy your school textbooks, materials and every day products Here!

Proof by induction - Fibonacci sequence

  • Thread starter Natasha1
  • Start date
  • #1
467
7
I need to proove by induction that:

1, 1, 2, 3, 5, 8, 13.....


if you do take f1*f3 - f2^2 you get 1
for the next in the series f2 you get f2*f4 - f3^2 you get -1
and so on...

You keep getting 1, -1, 1, -1 for ever.... and i need to proove that. Could someone please do it, or has anyone got a link on the internet to it? I have been looking for hours :-(


[tex](F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}[/tex]

Fn being a Fibonacci number

By convention F0 = 0, F1 = 1, so that F2 = 1.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
955
Natasha1 said:
I need to proove by induction that:

1, 1, 2, 3, 5, 8, 13.....

if you do take f1*f3 - f2^2 you get 1
for the next in the series f2 you get f2*f4 - f3^2 you get -1
and so on...

You keep getting 1, -1, 1, -1 for ever.... and i need to proove that. Could someone please do it, or has anyone got a link on the internet to it? I have been looking for hours :-(


[tex](F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}[/tex]

Fn being a Fibonacci number

By convention F0 = 0, F1 = 1, so that F2 = 1.
Okay, It's clearly true for n= 1 as you showed.

Now, assume that is true for some number k:
[tex](F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}[/tex]
Now look at what happens for k+1:
[tex](F_{k+1} \cdot F_{k+1+2}) - (F_{k+1+1})^2 = F_{k+1}\cdot F_{k+3}- F_{k+2}^2[/tex]

Of course [itex]F_{k+3}= F_{k+1}+F_{k+2}[/itex] and [itex]F_{k+2}= F_k+ F_{k+1}[/itex]. Substitue those into the formula above (the one with Fk+3 in it) and see if you can't rearrange it to get something like you "inductive hypothesis" which you can then replace with (-1)n.
 
  • #3
467
7
HallsofIvy said:
Okay, It's clearly true for n= 1 as you showed.

Now, assume that is true for some number k:
[tex](F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}[/tex]
Now look at what happens for k+1:
[tex](F_{k+1} \cdot F_{k+1+2}) - (F_{k+1+1})^2 = F_{k+1}\cdot F_{k+3}- F_{k+2}^2[/tex]

Of course [itex]F_{k+3}= F_{k+1}+F_{k+2}[/itex] and [itex]F_{k+2}= F_k+ F_{k+1}[/itex]. Substitue those into the formula above (the one with Fk+3 in it) and see if you can't rearrange it to get something like you "inductive hypothesis" which you can then replace with (-1)n.

Is this good? Please see attached picture
 

Attachments

  • #4
VietDao29
Homework Helper
1,423
2
Natasha1 said:
Is this good? Please see attached picture
Aaarrrrggg, why don't you just LaTeX? I've been waiting for that attachment to be approved for ages. :cry: :cry: :cry:
 
  • #5
467
7
VietDao29 said:
Aaarrrrggg, why don't you just LaTeX? I've been waiting for that attachment to be approved for ages. :cry: :cry: :cry:
Who approves these documents anyway?!?! It takes not weeks but months!

Anyway...

Here is what I've done, if not please correct me :-):

Since there is a [tex]k\geq 2[/tex] such as,
[tex]F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}[/tex]
Then proof it hold for [tex]k+1[/tex]. But the expression,
[tex]F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))[/tex]
But,
[tex]F(k)^2-F(k+1)(k-1)=(-1)^{k-1}[/tex]
Thus,
[tex]F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k[/tex]
Thus, it hold true for [tex]k+1[/tex].
 
  • #6
148
0
You haven't proven anything yet. Start by showing that the formula is valid for [itex]k=0[/itex], i.e. that [itex]F_0 \cdot F_{2}-F_{1}^2=(-1)^{1}[/itex]. Then prove [itex]F_{k+1} \cdot F_{k+3}-F_{k+2}^2=(-1)^{k+1}[/itex] knowing that [itex]F_k \cdot F_{k+2}-F_{k+1}^2=(-1)^{k+1}[/itex] and [itex]F_k+F_{k+1}=F_{k+2}[/itex].
 
  • #7
VietDao29
Homework Helper
1,423
2
Natasha1 said:
But,
[tex]F(k)^2-F(k+1)(k-1)=(-1)^{k-1}[/tex]
Thus,
[tex]F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k[/tex]
Thus, it hold true for [tex]k+1[/tex].
Why? This is what you have to prove!!! You cannot assume things like that. You must prove it.
The idea for Proof By Induction is that say if the statement holds for n = 1, and you can prove that if the statement holds for n = k then it also holds for n = k + 1. Then the statement holds for every [tex]n \geq 1[/tex]. Why? Besause say the statement is true for n = 1 (you can test to see if it's true), then the statement is also true for n = 1 + 1 = 2.
And because the statement is true for n = 2, it's also true for n = 2 + 1 = 3, and because the statement is true for n = 3, it's also true for n = 3 + 1 = 4, and so on... So the statement is true for all n greater than or equal to 1.
--------------
Example:
Prove that:
[tex]\sum_{i = 1} ^ n i = \frac{n (n + 1)}{2}, \ n \geq 1[/tex]
Proof:
Step 1: For n = 1, we have:
LHS : [tex]\sum_{i = 1} ^ 1 i = 1[/tex]
RHS : [tex]\frac{1 (1 + 1)}{2} = \frac{2}{2} = 1[/tex]
So LSH = RHS, hence the equation holds for n = 1.
Step 2: Assume that the equation is true for n = k (inductive hypothesis), we have:
[tex]\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}[/tex]
Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:
[tex]\sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}[/tex]
So we have:
[tex]\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}[/tex] (this is our inductive hypothesis, we'll start from it)
[tex]\Leftrightarrow \sum_{i = 1} ^ k (i) + k + 1 = \frac{k (k + 1)}{2} + k + 1[/tex]
[tex]\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{k (k + 1) + 2 (k + 1)}{2}[/tex]
[tex]\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}[/tex] (factor (k + 1) out in the RHS)
Hence the equation holds true for n = k + 1.
--------------
This means you have proven that:
If the statement is true for n = k => it's true for n = k + 1
You have tested that it's true for n = 1 (the first step)
So the equation holds for n = 1 => it holds for n = 1 + 1 = 2 => it holds for n = 2 + 1 = 3 => it holds for n = 3 + 1 = 4 => ... => it holds for all n greater than or equal to 1.
Can you get this?
--------------
Back to your problem, now you have to test to see if it's true for n = 0 first, then you have to prove
IF [tex](F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}[/tex]
THEN
[tex](F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}[/tex]
Can you go from here? :)
Hint: You can re-read HallsofIvy's post to have some ideas on how to start off the problem.
 
Last edited:
  • #8
467
7
VietDao29 said:
Why? This is what you have to prove!!! You cannot assume things like that. You must prove it.
The idea for Proof By Induction is that say if the statement holds for n = 1, and you can prove that if the statement holds for n = k then it also holds for n = k + 1. Then the statement holds for every [tex]n \geq 1[/tex]. Why? Besause say the statement is true for n = 1 (you can test to see if it's true), then the statement is also true for n = 1 + 1 = 2.
And because the statement is true for n = 2, it's also true for n = 2 + 1 = 3, and because the statement is true for n = 3, it's also true for n = 3 + 1 = 4, and so on... So the statement is true for all n greater than or equal to 1.
--------------
Example:
Prove that:
[tex]\sum_{i = 1} ^ n i = \frac{n (n + 1)}{2}, \ n \geq 1[/tex]
Proof:
Step 1: For n = 1, we have:
LHS : [tex]\sum_{i = 1} ^ 1 i = 1[/tex]
RHS : [tex]\frac{1 (1 + 1)}{2} = \frac{2}{2} = 1[/tex]
So LSH = RHS, hence the equation holds for n = 1.
Step 2: Assume that the equation is true for n = k (inductive hypothesis), we have:
[tex]\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}[/tex]
Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:
[tex]\sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}[/tex]
So we have:
[tex]\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}[/tex] (this is our inductive hypothesis, we'll start from it)
[tex]\Leftrightarrow \sum_{i = 1} ^ k (i) + k + 1 = \frac{k (k + 1)}{2} + k + 1[/tex]
[tex]\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{k (k + 1) + 2 (k + 1)}{2}[/tex]
[tex]\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}[/tex] (factor (k + 1) out in the RHS)
Hence the equation holds true for n = k + 1.
--------------
This means you have proven that:
If the statement is true for n = k => it's true for n = k + 1
You have tested that it's true for n = 1 (the first step)
So the equation holds for n = 1 => it holds for n = 1 + 1 = 2 => it holds for n = 2 + 1 = 3 => it holds for n = 3 + 1 = 4 => ... => it holds for all n greater than or equal to 1.
Can you get this?
--------------
Back to your problem, now you have to test to see if it's true for n = 0 first, then you have to prove
IF [tex](F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}[/tex]
THEN
[tex](F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}[/tex]
Can you go from here? :)
Hint: You can re-read HallsofIvy's post to have some ideas on how to start off the problem.

Is this good?

Step 1: For n = 1, we have


[tex](F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1[/tex]


Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

[tex](F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}[/tex]

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

[tex](F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}[/tex]

So we have:

[tex](F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}[/tex]
[tex](F_k \cdot F_{k+2}) - (F_{k+1})^2 + k+1= (-1)^{k+1} + k+1[/tex]
Could someone write what goes here please?
.
.
[tex](F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}[/tex]

Hence the equation holds true for n = k + 1
 
Last edited:
  • #9
matt grime
Science Advisor
Homework Helper
9,395
3
No, that is not right. Firstly, you need to put inexplicitly what F_1,F_2 and F_3 are to prove the base case, and no we are not going to put in the missing steps for you since that would be 'doign your homework for you' and that is not allowed.


Start with the expression for k+1 (do not put in =(-1)^{whatever}) just put in the LHS, now, what do you know about the fibonacci sequence? use that to get rid of the F_{k+3} and now try t manipulate it to get it ina form that lets you use the inductive hypothesis (i.e. the identity for k)
 
  • #10
467
7
Any better???

Step 1: For n = 1, we have

[tex](F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1[/tex]

Where f_1=1m f_2 = 1, f_3 = 2
Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

[tex](F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}[/tex]

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

[tex](F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 [tex]

So we have:

Since there is a [tex]k\geq 2[/tex] such as,
[tex]F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}[/tex]

Then proof it hold for [tex]k+1[/tex].

But the expression,
[tex]F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))[/tex]
But,
[tex]F(k)^2-F(k+1)(k-1)=(-1)^{k-1}[/tex]
Thus,
[tex]F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k[/tex]
Thus, it hold true for [tex]k+1[/tex].

[tex](F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}[/tex]

Hence the equation holds true for n = k + 1[/QUOTE]
 
Last edited:
  • #11
VietDao29
Homework Helper
1,423
2
Natasha1 said:
But,
[tex]F(k)^2-F(k+1)(k-1)=(-1)^{k-1}[/tex]
Thus,
[tex]F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k[/tex]
No, it's still wrong. How can you go from the former equation to the latter one? You have to prove it, why is it true? You cannot just claim that it's true without giving any proof.
Ok, what you have to do know is to use the Fibonacci sequence's property, i.e:
Fn + 2 = Fn + Fn + 1 to rearrange the expression [tex]F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2[/tex] to something like this: [tex]( F_{k} \cdot F_{k+2}) - (F_{k+1})^2) \cdot \mbox{something}[/tex]
I personally think that you should read the chapter about Proof by Induction in your book again, find some examples there, try to read, and think thoroughly to understand why did the author do that, and how can he use Proof by Induction. And when you understand it a bit better, try to tackle this problem again.
 
Last edited:
  • #12
467
7
If someone could be king enough to have a read through my induction proof attached and mention if there are any mistakes. Thanks
 
Last edited:

Related Threads on Proof by induction - Fibonacci sequence

  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
1
Views
15K
  • Last Post
Replies
1
Views
825
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
8
Views
1K
Top