Induction Proof with Fibonacci

Question

How do I prove this?

For the Fibonacci numbers defined by $f_1=1$, $f_2=1$, and $f_n = f_{n-1} + f_{n-2}$ for $n ≥ 3$, prove that $f^2_{n+1} - f_{n+1}f_n - f^2_n = (-1)^n$ for all $n≥ 1$.

Answer 1

You can reduce it immediately to Cassini's identity: $$ f^2_{n+1} - f_{n+1}f_n - f^2_n = f_{n+1}(f_{n+1} - f_n) - f^2_n = f_{n+1}f_{n-1} - f^2_n = (-1)^n $$ Cassini's identity has a nice proof using determinants: $$ f_{n-1}f_{n+1} - f_n^2 =\det\left[\begin{matrix}f_{n+1}&f_n\\f_n&f_{n-1}\end{matrix}\right] =\det\left[\begin{matrix}1&1\\1&0\end{matrix}\right]^n =\left(\det\left[\begin{matrix}1&1\\1&0\end{matrix}\right]\right)^n =(-1)^n $$ This matrix formulation of Fibonacci numbers is well worth knowing.

Answer 2

A slightly faster proof comes from noticing that

$$q(x,y) = x^2-xy-y^2 = (y-x)^2-y(x-y)-y^2 = q(y-x,y)$$ and: $$ q(-x,y) = x^2+xy-y^2 = -q(y,x) $$ hence: $$ q(f_{n+1},f_n) = q(-f_{n-1},f_n) = -q(f_n,f_{n-1}) = \ldots = (-1)^n q(1,0).$$

Answer 3

The recursion can also be written as $$ f_{n+2}=f_{n+1}+f_n $$ So you want to prove that the formula holds for $n=1$ (just plug in the value) and that, if it holds for $n$, then it holds for $n+1$.

Thus, assume you know that $f^2_{n+1} - f_{n+1}f_n - f^2_n = (-1)^n$. Then $$ f_{n+2}^2-f_{n+2}f_{n+1}-f_{n+1}^2= (f_{n+1}+f_n)^2-(f_{n+1}+f_n)f_{n+1}-f_{n+1}^2 $$ Expand and apply the induction hypothesis

Answer 4

• Base Case:

For $n = 1$:

$$f_2^2 - f_2f_1 - f_1^2 = (-1)^1$$

$$(1)^2 - (1)(1) - (1)^2 = -1$$

$$-1 = -1$$

---

• Induction Step:

Assume that the given statement is true. We now try to prove that it holds true for $n+1$:

$$f_{n+2}^2 - f_{n+2}f_{n+1} - f_{n+1}^2 = (-1)^{n+1}$$

Typically you choose one side and try to get to the other side. I will choose the left side:

$$f_{n+2}^2 - f_{n+2}f_{n+1} - f_{n+1}^2 = (f_{n+1} + f_{n})^2 - (f_{n+1} + f_{n})(f_{n+1}) - f_{n+1}^2$$

$$= f_{n+1}^2 + 2f_{n+1}f_{n} + f_{n}^2 - f_{n+1}^2 - f_{n+1}f_{n} - f_{n+1}^2$$

$$= f_{n}^2 + f_{n+1}f_{n} - f_{n+1}^2$$

$$= (-1)(f_{n+1}^2 - f_{n+1}f_{n} - f_{n}^2)$$

$$= (-1)(-1)^n$$

$$= (-1)^{n+1}$$

Answer 5

Subscripts and superscripts are a real nuisance in maths - mathematicians tend to privilege intense efficiency and minimalism of notation over readability - it makes sense in the long run, but for a learner it is quite confusing.

Try reading any subscript as "the first $f$, the second $f$" etc., and any superscript as you normally would; squared, cubed etc.

In plain english, the question asks:

"Given a sequence where the first number is $1$, the second is $1$, and after that, each number is equal to the sum of the previous two numbers (so $f_3=1+1=2$), then prove that for the $n$th number in the sequence, if you take the square of the next number, subtract the product of that next number and the $n$th number, then subtract the square of the $n$th number, you will get either plus or minus $1$, depending on whether $n$ was even or odd."

Have a read of that paragraph, try and understand where I got each translation from, then read on!

To prove this by induction, we follow the same basic plan:

1) Base case. Is it true for $n=1$? Well, $$f_2^2-f_2f_1-f_1^2=1^2-1\cdot1-1^2=-1=(-1)^1$$ So yes, it is true.

2) Hypothesis. You should always state your hypothesis clearly, as it helps you and your reader/marker see exactly what you needed to get to the conclusion. Here, you say "Suppose $f_{n+1}^2-f_{n+1}f_n-f_n^2=(-1)^n$ for $n=k$"; that is, assume the equation works for some number $k$.

3) Now show, using your assumption, that it must hold for $k+1$. That is, we want to show that when $n=k+1$, the sentence $f_{n+2}^2-f_{n+2}f_{n+1}-f_{n+1}^2$ holds. We can do this by relating $f_{n+2}$ to $f_{n+1}$ and $f_n$ using the rule by which we constructed the sequence in the first place. As other answers have shown, you can then take the equation you want to prove, rearrange, substitute the construction rule, and apply the hypothesis to conclude it really does work for $n=k+1$.

4) Conclude! Since it holds for $n=1$, and given it holds for any number $n=k$, it will also hold for $n=k+1$, it must hold for all natural numbers. The End.

Answer 6

the inductive step: $$ f^2_{n+1} - f_{n+1}f_n - f^2_n = (-1)^n \Leftrightarrow \\ f_{n+1}f_{n-1} - f_n^2 =(-1)^n \Leftrightarrow \\ (f_{n+2}-f_n)(f_{n+1}-f_n) -f_n^2 = (-1)^n \Leftrightarrow \\ f_{n+2}f_{n+1}-f_nf_{n+3} = (-1)^n \Leftrightarrow \\ f_{n+1}^2+f_nf_{n+1}-f_nf_{n+1}-f_nf_{n+2}=(-1)^n \Leftrightarrow \\ f_{n+2}f_n-f_{n+1}^2 = (-1)^{n+1} \Leftrightarrow \\ f_{n+2}^2-f_{n+2}f_{n+1}-f_{n+1}^2 =(-1)^{n+1} $$