Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I can't seem to solve this problem. It is: The Fibonacci numbers $F(0), F(1), F(2),\dots $ are defined as follows:

$F(0) ::= 0$

$F(1) ::= 1$

$F(n) ::= F(n-1) + F(n-2)\qquad(\forall n \ge 2 $)

Thus, the first Fibonacci numbers are $0, 1, 1, 2, 3, 5, 8, 13, and, 21$. Prove by induction that $\forall n \ge1$,

$F(n-1) * F(n+1) – F(n)^2 = (-1)^n$

I'm stuck, as I my induction hypothesis was the final equation, and I replaced n in it with n+1, which gave me:

$F(n) * F(n+2) – F(n+1)^2 = (-1)^{n+1}$

I then tried simplifying this using the first equation, which gave me: $[(F(n-1) + F(n-2)] * F(n+2) — F(n+1)^2 = (-1)^{n+1}$

I then tried replacing $n$ in the first equation with $n+1$, but that just gave me

$2F(n-1) + F(n-2)$

I'm really not sure how to proceed, and I was hoping for some help. I'm new to induction and I'm hoping this is just an algebra problem and not a problem with the method, but any help would be greatly appreciated.

share|improve this question
1  
You've written the wrong thing as a sum. $F_n\cdot F_{n+2} - F_{n+1}^2 = F_n(F_{n+1}+F_n) - F_{n+1}(F_n + F_{n-1})$. –  Daniel Fischer Oct 12 '13 at 22:07

4 Answers 4

You have written the wrong Fibonacci number as a sum. You know something about $F_{n-1},\, F_n$ and $F_{n+1}$ by the induction hypothesis, while $F_{n+2}$ is new. So you should write $F_{n+2} = F_{n+1} + F_n$. And in the other summand, write one factor too as a sum,

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

can be easily and fruitfully related to the induction hypothesis.

share|improve this answer

Just to be contrary, here's a (more instructive?) proof that isn't directly by induction:

Lemma. Let $A$ be the $2\times 2$ matrix $\begin{pmatrix}1&1\\1&0\end{pmatrix}$. Then $A^n= \begin{pmatrix}F_{n+1} & F_n \\ F_n & F_{n-1}\end{pmatrix}$ for every $n\ge 1$.

This can be proved by induction on $n$ since $$A\begin{pmatrix}F_n & F_{n-1} \\ F_{n-1} & F_{n-2}\end{pmatrix} = \begin{pmatrix}F_n+F_{n-1} & F_{n-1}+F_{n-2} \\ F_n & F_{n-1}\end{pmatrix} = \begin{pmatrix}F_{n+1} & F_n \\ F_n & F_{n-1}\end{pmatrix}$$

Now, $F_{n+1}F_{n-1}-F_n^2$ is simply the determinant of $A^n$, which is $(-1)^n$ because the determinant of $A$ is $-1$.

share|improve this answer

Basis: $n = 1$

$$F_{n-1} \cdot F_{n+1} - F_{n}^2 = (-1)^n$$ $$F_{0} \cdot F_{2} - F_{1}^2 = (-1)^n$$ $$0 \cdot 1 - 1 = -1$$ $$-1 = -1 \text{, which is true}$$

Inductive hypothesis: $n=k$

We assume that the statement holds for some number $k$

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

Inductive step: $n = k+1$

We need to prove that the following statement holds

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

Starting from the inductive hypothesis we have:

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

Multiply both sides by $-1$

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

Using the property og Fibonacci numbers we have:

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

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

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

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

Q.E.D.

Note that his identity is called Cassini itentity for Fibonacci Numbers, which is a generalisation of the Catalan identity for Fibonacci Numbers, which states:

$$F_n^2 -F_{n-r}F_{n+r} = (-1)^{n-r}F_r^2$$

share|improve this answer
    
Seems wrong to me. You are assuming what you want to prove, and then deriving that $(-1)^{k+1}=(-1)^{k+1}$. You need to start with the induction assumption for $k$ and prove it for $k+1$. Perhaps your math can be rearranged to provide this proof. –  marty cohen Oct 13 '13 at 1:18
    
I don't think it's wrong at all. We started and using the hypothesis and algebraic transformation we reached something which is true, meaning that we proved the inductive step. Anyway I edit the answer and I hope it's better and clearer now. –  Stefan4024 Oct 13 '13 at 1:49

The inductive step is easiest to do by considering: $$ (F_n F_{n +2} - F_{n + 1}^2) + (F_{n - 1} F_{n + 1} - F_n^2) $$ I.e., adding up cases $n$ and $n + 1$. Massaging this with the Fibonacci recurrence $F_{n + 1} = F_{n + 2} - F_n$ reduces to zero, so you know they have the same absolute value and alternating signs.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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