Proof by induction - Fibonacci sequence

[Natasha1]

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 :-(


$$(F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}$$

Fn being a Fibonacci number

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

 

[HallsofIvy]

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 :-(


$$(F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}$$

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:
$$(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$$
Now look at what happens for k+1:
$$(F_{k+1} \cdot F_{k+1+2}) - (F_{k+1+1})^2 = F_{k+1}\cdot F_{k+3}- F_{k+2}^2$$

Of course $F_{k+3}= F_{k+1}+F_{k+2}$ and $F_{k+2}= F_k+ F_{k+1}$. Substitue those into the formula above (the one with F_k+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)ⁿ.

 

[Natasha1]

Okay, It's clearly true for n= 1 as you showed.

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

Of course $F_{k+3}= F_{k+1}+F_{k+2}$ and $F_{k+2}= F_k+ F_{k+1}$. Substitue those into the formula above (the one with F_k+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)ⁿ.

Is this good? Please see attached picture

 

[VietDao29]

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.

 

[Natasha1]

Aaarrrrggg, why don't you just LaTeX? I've been waiting for that attachment to be approved for ages.

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 $$k\geq 2$$ such as,
$$F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}$$
Then proof it hold for $$k+1$$. But the expression,
$$F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))$$
But,
$$F(k)^2-F(k+1)(k-1)=(-1)^{k-1}$$
Thus,
$$F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k$$
Thus, it hold true for $$k+1$$.

 

[durt]

You haven't proven anything yet. Start by showing that the formula is valid for $k=0$, i.e. that $F_0 \cdot F_{2}-F_{1}^2=(-1)^{1}$. Then prove $F_{k+1} \cdot F_{k+3}-F_{k+2}^2=(-1)^{k+1}$ knowing that $F_k \cdot F_{k+2}-F_{k+1}^2=(-1)^{k+1}$ and $F_k+F_{k+1}=F_{k+2}$.

 

[VietDao29]

But,
$$F(k)^2-F(k+1)(k-1)=(-1)^{k-1}$$
Thus,
$$F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k$$
Thus, it hold true for $$k+1$$.

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 $$n \geq 1$$. 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:
$$\sum_{i = 1} ^ n i = \frac{n (n + 1)}{2}, \ n \geq 1$$
Proof:
Step 1: For n = 1, we have:
LHS : $$\sum_{i = 1} ^ 1 i = 1$$
RHS : $$\frac{1 (1 + 1)}{2} = \frac{2}{2} = 1$$
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:
$$\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}$$
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:
$$\sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}$$
So we have:
$$\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}$$ (this is our inductive hypothesis, we'll start from it)
$$\Leftrightarrow \sum_{i = 1} ^ k (i) + k + 1 = \frac{k (k + 1)}{2} + k + 1$$
$$\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{k (k + 1) + 2 (k + 1)}{2}$$
$$\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}$$ (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 $$(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$$
THEN
$$(F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$$
Can you go from here? :)
Hint: You can re-read HallsofIvy's post to have some ideas on how to start off the problem.

 

[Natasha1]

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 $$n \geq 1$$. 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:
$$\sum_{i = 1} ^ n i = \frac{n (n + 1)}{2}, \ n \geq 1$$
Proof:
Step 1: For n = 1, we have:
LHS : $$\sum_{i = 1} ^ 1 i = 1$$
RHS : $$\frac{1 (1 + 1)}{2} = \frac{2}{2} = 1$$
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:
$$\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}$$
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:
$$\sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}$$
So we have:
$$\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}$$ (this is our inductive hypothesis, we'll start from it)
$$\Leftrightarrow \sum_{i = 1} ^ k (i) + k + 1 = \frac{k (k + 1)}{2} + k + 1$$
$$\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{k (k + 1) + 2 (k + 1)}{2}$$
$$\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}$$ (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 $$(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$$
THEN
$$(F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$$
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


$$(F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1$$


Hence the equation holds for n = 1

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

$$(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$$

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:

$$(F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$$

So we have:

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

Hence the equation holds true for n = k + 1

 

[matt grime]

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 let's you use the inductive hypothesis (i.e. the identity for k)

 

[Natasha1]

Any better?

Step 1: For n = 1, we have

$$(F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1$$

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:

$$(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$$

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 $$k\geq 2$$ such as,
$$F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}$$

Then proof it hold for $$k+1$$.

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

$$(F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$$

Hence the equation holds true for n = k + 1[/QUOTE]

 

[VietDao29]

But,
$$F(k)^2-F(k+1)(k-1)=(-1)^{k-1}$$
Thus,
$$F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k$$

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:
F^{n + 2} = Fⁿ + F^{n + 1} to rearrange the expression $$F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2$$ to something like this: $$( F_{k} \cdot F_{k+2}) - (F_{k+1})^2) \cdot \mbox{something}$$
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.

 

[Natasha1]

If someone could be king enough to have a read through my induction proof attached and mention if there are any mistakes. Thanks