Vtyjkyuk

Consider the Fibonacci sequence $a_n$
Use mathematical induction to prove that
$a_n+1a_n-1=(a_n)^2+(-1)^n$

So far, I have tested the base case $n=1$ which is true. I am stuck on the inductive step where I plug in $k=n+1$.

$a_n+2a_n=(a_n+1)^2+(-1)^n+1$

$a_n+2a_n=(a_n+1)^2-(-1)^n$

I am unsure what the next step to take is.

Recall that:
$a_1=1$,$a_2=1$,$a_3=2$ .

For $n=2$:
$$
a_3a_1=a_2^2+(-1)^2=2
$$

We assume the hypothesis valid for $n=k$, such that:
$$
a_k+1a_k-1=a_k^2+(-1)^k
$$

Let's find the value of $a_k+2a_k$. We can use the Fibonacci recursion: $a_k+2=a_k+1+a_k$. Therefore:
$$
a_k+2a_k=(a_k+1+a_k)a_k=a_k+1a_k+a_k^2
$$
From the hypothesis:
$$
a_k+1a_k-1=a_k^2+(-1)^k Rightarrow a_k^2 = a_k+1a_k-1-(-1)^k
$$

Thus:
$$
a_k+2a_k=(a_k+1+a_k)a_k=a_k+1a_k+a_k+1a_k-1-(-1)^k
$$
$$
a_k+2a_k=a_k+1a_k+a_k+1a_k-1+(-1)^k+1=a_k+1(a_k+a_k-1)+(-1)^k+1
$$
Apply Fibonacci recursion again to find:
$$
a_k+2a_k=a_k+1^2+(-1)^k+1
$$

For $n=1$, $~~a_2a_0-a_1^2=-1$, so the statement is true for $n=1$. Let, the statement $P(n):$ $ a_n+1a_n-1-a_n^2=(-1)^n$ is true for $n=m$. We need to show that $P(m+1)$ is true. $$a_m+2a_m-a_m+1^2=(-1)^m+1 $$

Using recurrence relation on $a_m+2=a_m+1+a_m$ and $a_m=a_m+1-a_m-1$,
$$requirecancela_m+2a_m-a_m+1^2=(a_m+1+a_m)(a_m+1-a_m-1)-a_m+1^2\ = cancela_m+1^2+a_ma_m+1-a_m+1a_m-1-a_ma_m-1-cancela_m+1^2\=a_m(a_m+1-a_m-1)-a_m+1a_m-1= a_m^2-a_m+1a_m-1=-(a_m+1a_m-1-a_m^2)=(-1)^m+1 $$
as by inductive argument $a_m+1a_m-1-a_m^2=(-1)^m$. Hence done!

The base hypothesis is obviously true: $0cdot1-1^2=(-1)^1$.

Now the given formula hints to establish
$$F_n+1F_n-1-F_n^2=-(F_nF_n-2-F_n-1^2).$$

If we expand $F_n+1$ we get
$$F_nF_n-1+F_n-1^2-F_n^2=-F_nF_n-2+F_n-1^2.$$

Then regrouping the two terms with $F_n$,
$$F_n(F_n-1-F_n)+F_n-1^2=-F_nF_n-2+F_n-1^2$$

and we are done.