Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I can't seem to solve this problem. It is:

The Fibonacci numbers $F(0), F(1), F(2),\dots $ are defined as follows:

\begin{align} F(0) &::= 0 \\ F(1) &::= 1 \\ F(n) &::= F(n-1) + F(n-2)\qquad(\forall n \ge 2)\end{align}

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) \cdot 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) \cdot 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)]\cdot 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|cite|improve this question
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

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|cite|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 on 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}$$


Note that his identity is called Cassini identity for Fibonacci Numbers, which is a generalization 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|cite|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

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|cite|improve this answer
@Ralph I'm not sure why that edit was approved, but I do not feel it should have been. You added far more to the Answer than was originally written; Daniel's voice was essentially drowned out by your own. If you feel it is worthwhile to include an entire proof (but there is already Stefan4024's answer, so...) , I think you should write your own answer. – pjs36 Jun 10 at 21:31
Sure I can do that. I was surprised it let me edit it in the first place. The Stefan answer seems to be done backwards. – Ralph Yozzo Jun 10 at 23:12

Fibonacci Recurrence Definition: $$F_{n} = F_{n-1} + F_{n-2} \, (where \, n \ge 2), \, and \, F_{0}=0, F_{1}=1$$

Theorem: $$\forall n\ge 1: (F_{n+1}\cdot F_{n-1}) - F_{n}^2 = (-1)^n$$

Proof by Induction:

Base step: $n = 1$

$$F_{2} \cdot F_{0} - F_{1}^2 = (-1)^n$$ $$1 \cdot 0 - 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+2}\cdot F_{k}) - F_{k+1}^2 = (-1)^{(k+1)}$$

But this can be rewritten as:

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

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

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

since $\forall n:-1^{n+1} \cdot -1 = -1^{n} $

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

share|cite|improve this answer

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|cite|improve this answer

Your Answer


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.