Fibonacci Numbers proof, circular reasoning?

Question

I got this from "Number Theory" by George E. Andrews (1971), at the end of the first chapter, he asks for proofs by mathematical induction about Fibonacci Numbers as exercices. In one of them I am asked to show that

$$(\forall \, n \in \Bbb Z^+)((F_{n+1})^2-F_nF_{n+2}=(-1)^n)$$

which has already has been asked on Math S.E.: "Fibonacci numbers and proof by induction" but I am not looking for a complete solution here; rather, since I am learning the subject on my own I would appreciate it if someone could simply tell me if my reasoning is correct, it does not "feel" concrete to me.

Going through the usual steps I first check that the base case $F_2^2-F_1F_3=1-2=(-1)^1$ is true such that the inductive step can be taken. Then, assuming $(F_{k+1})^2-F_kF_{k+2}=(-1)^k$ is true, I try to show that it implies that $(F_{k+2})^2-F_{k+1}F_{k+3}=(-1)^{k+1}$ is also true.

Then, doing a bit of algebra I get,

$$\begin{align} (F_{k+2})^2-F_{k+1}F_{k+3} & = (-1)^{k+1}=(-1)^k(-1)\\ & = ((F_{k+1})^2-F_kF_{k+2})(-1)\\ & = F_kF_{k+2}-(F_{k+1})^2\\ (F_{k+2})^2-F_{k+1}F_{k+3} + (F_{k+1})^2-F_kF_{k+2} & = 0\\ (F_{k+2})^2-F_{k+1}F_{k+3} + (-1)^k & = 0\\ (F_{k+2})^2-F_{k+1}F_{k+3} & = -(-1)^k = (-1)(-1)^k\\ & = (-1)^{k+1}\\ \end{align}$$ $$\tag*{$\blacksquare$}$$

I am not sure about this, it feels like circular reasoning, is it?

Thanks a lot for the valuable input!

Answer 1

As @ElliotG pointed out, you cannot begin with what you want to prove. Instead, if you want to show an equality, begin with the left hand side of the inequality, then do things with it until you arrive at the right hand side.

In the induction step you know that $F_{n+2} = F_{n+1} + F_n$ and $F_{k+1}^2-F_k F_{k+2} = (-1)^k$. So start with $$ F_{k+1}^2 - F_{k+1}F_{k+3} = \dots\,, $$ and work your way, using the known identities, until you arrive at $$ \dots = (-1)^{k+1}\,.$$ Then you will have proven the induction step.

Answer 2

Your intuition was correct ... This is indeed a circular proof, as in your first step you assume exactly what you need to prove.

Instead, you should start with the left-hand side and, using both the inductive hypothesis, as well as the definition of the fibonacci numbers, try to end up with the right-hand side.

Answer 3

Yes, your answer is wrong, because you assume that $(F_{k+2})^2 - F_{k+1}F_{k+3} = (-1)^{k+1}$ but it's what you want to prove. By the way, here is the algebra:

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

Answer 4

The non-inductive proof is interesting as well.

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

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

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

Hence signs flip. We can descend all the way to $F_2^2 - F_1F_3 = -1$ From $n+1$ to $2$, we have $n-1$ changes in sign. So we get $F_{n+1}^2 - F_nF_{n+2} = -1(-1)^{n-1} = (-1)^n$