Show that $z_n$ is a perfect square if $z_0 = z_1 = 1$ and $z_{n+1} = 7z_n − z_{n−1} − 2$ [closed]

Solution 1:

From $$z_{n+1} = 7z_n − z_{n−1} − 2$$ $$z_{n} = 7z_{n-1} − z_{n−2} − 2$$ we have $$z_{n+1}-z_{n}=7z_n − 8z_{n-1} + z_{n−2} \iff z_{n+1}-8z_{n}+8z_{n-1} - z_{n−2}=0$$ This homogeneous recurrence has this characteristic polynomial $$x^3-8x^2+8x-1=0$$ with solutions $1, \frac{7-3\sqrt{5}}{2}, \frac{7+3\sqrt{5}}{2}$ and general solution $$z_n = A\cdot (1)^n+B\cdot \left(\frac{7-3\sqrt{5}}{2}\right)^n+C\cdot \left(\frac{7+3\sqrt{5}}{2}\right)^n$$ Now, by solving $$1=A+B+C\\ 1=A+B\cdot\left(\frac{7-3\sqrt{5}}{2}\right)+C\cdot\left(\frac{7+3\sqrt{5}}{2}\right)\\ 4=A+B\cdot\left(\frac{7-3\sqrt{5}}{2}\right)^2+C\cdot\left(\frac{7+3\sqrt{5}}{2}\right)^2$$ we have

$$z_n = \frac{2}{5}+\left(\frac{3+\sqrt{5}}{10}\right)\cdot \left(\frac{7-3\sqrt{5}}{2}\right)^n+\left(\frac{3-\sqrt{5}}{10}\right)\cdot \left(\frac{7+3\sqrt{5}}{2}\right)^n \tag{1}$$

Now $$\frac{7-3\sqrt{5}}{2}=\frac{14-2\cdot3\sqrt{5}}{4}= \frac{9-2\cdot3\sqrt{5}+5}{4}=\left(\frac{3-\sqrt{5}}{2}\right)^2$$ $$\frac{7+3\sqrt{5}}{2}=\frac{14+2\cdot3\sqrt{5}}{4}= \frac{9+2\cdot3\sqrt{5}+5}{4}=\left(\frac{3+\sqrt{5}}{2}\right)^2$$ as a result, $(1)$ becomes $$z_n = \frac{2}{5}+\left(\frac{3+\sqrt{5}}{10}\right)\cdot \left(\frac{3-\sqrt{5}}{2}\right)^{2n}+\left(\frac{3-\sqrt{5}}{10}\right)\cdot \left(\frac{3+\sqrt{5}}{2}\right)^{2n}=\\ \frac{2}{5}+\frac{1}{5}\cdot \left(\frac{3-\sqrt{5}}{2}\right)^{2n-1}+\frac{1}{5}\cdot \left(\frac{3+\sqrt{5}}{2}\right)^{2n-1} \tag{2}$$ Also $$\frac{3+\sqrt{5}}{2}=\left(\frac{1+\sqrt{5}}{2}\right)^2$$ $$\frac{3-\sqrt{5}}{2}=\left(\frac{1-\sqrt{5}}{2}\right)^2$$ and finally $$\color{red}{z_n} = \frac{2}{5}+\frac{1}{5}\cdot \left(\frac{1-\sqrt{5}}{2}\right)^{2(2n-1)}+\frac{1}{5}\cdot \left(\frac{1+\sqrt{5}}{2}\right)^{2(2n-1)}=\\ -\frac{2}{5}\cdot\left(\frac{1-\sqrt{5}}{2}\right)^{2n-1}\left(\frac{1+\sqrt{5}}{2}\right)^{2n-1}+\frac{1}{5}\cdot \left(\frac{1-\sqrt{5}}{2}\right)^{2(2n-1)}+\frac{1}{5}\cdot \left(\frac{1+\sqrt{5}}{2}\right)^{2(2n-1)}=\\ \frac{1}{5}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{2n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{2n-1}\right)^2=\\ \color{red}{\left(F_{2n-1}\right)^2}$$

Solution 2:

I want to show that $z_n=F_{2n-1}^2$ where $F_n$ is the $n^{th}$ Fibonacci number, starting with $F_1=1,\space F_2=1$. The equation $z_n=F_{2n-1}^2$ is true for $n=1,\space n=2,\space n=3$.

$z_3=F_5^2=25,\space z_2=F_3^2=4,\space z_1=F_1^2=1$ so $F_5^2=7F_3^2-F_1^2-2$.

So now I will prove by induction that $F_{2n+3}^2=7F_{2n+1}^2-F_{2n-1}^2-2\Rightarrow F_{2n+5}^2=7F_{2n+3}^2-F_{2n+1}^2-2$ but first the problem has to be transformed. $$F_{2n+3}^2=7F_{2n+1}^2-F_{2n-1}^2-2\quad(1)$$ $$F_{2n+3}^2+F_{2n-1}^2=7F_{2n+1}^2-2$$ $$(F_{2n+2}+F_{2n+1})^2+F_{2n-1}^2=7(F_{2n}+F_{2n-1})^2-2$$ $$(2F_{2n+1}+F_{2n})^2+F_{2n-1}^2=7(F_{2n}+F_{2n-1})^2-2$$ $$(3F_{2n}+2F_{2n-1})^2+F_{2n-1}^2=7(F_{2n}+F_{2n-1})^2-2$$ $$9F_{2n}^2+12F_{2n}F_{2n-1}+5F_{2n-1}^2=7F_{2n}^2+14F_{2n}F_{2n-1}+7F_{2n-1}^2-2$$ $$2F_{2n}^2-2F_{2n}F_{2n-1}-2F_{2n-1}^2=-2$$ $$F_{2n}^2-F_{2n}F_{2n-1}-F_{2n-1}^2=-1$$ $$F_{2n}^2-F_{2n-1}^2-F_{2n}F_{2n-1}=-1$$ $$(F_{2n}-F_{2n-1})(F_{2n}+F_{2n-1})-F_{2n}F_{2n-1}=-1$$ $$(F_{2n}-F_{2n-1})(F_{2n+1})-F_{2n}F_{2n-1}=-1$$ $$F_{2n+1}F_{2n}-F_{2n+1}F_{2n-1}-F_{2n}F_{2n-1}=-1$$ $$F_{2n+1}F_{2n}-F_{2n}F_{2n-1}-F_{2n+1}F_{2n-1}=-1$$ $$F_{2n}(F_{2n+1}-F_{2n-1})-F_{2n+1}F_{2n-1}=-1$$ $$F_{2n}^2-F_{2n+1}F_{2n-1}=-1$$ $$F_{2n+1}F_{2n-1}-F_{2n}^2=1\quad(2)$$ Since $(1)$ is true iff $(2)$ is true. It is sufficient to show that $F_{2n+1}F_{2n-1}-F_{2n}^2=1\Rightarrow F_{2n+3}F_{2n+1}-F_{2n+2}^2=1$. $$F_{2n+3}F_{2n+1}-F_{2n+2}^2=(F_{2n+2}+F_{2n+1})F_{2n+1}-F_{2n+2}^2\quad(3)$$ $$=(F_{2n+2}+F_{2n+1})F_{2n+1}-F_{2n+2}^2$$ $$=F_{2n+2}F_{2n+1}+F_{2n+1}^2-F_{2n+2}^2$$ $$=F_{2n+2}F_{2n+1}+F_{2n+1}^2-F_{2n+2}^2$$ $$=F_{2n+2}F_{2n+1}+F_{2n+1}^2-F_{2n+2}(F_{2n+1}+F_{2n})$$ $$=F_{2n+2}F_{2n+1}+F_{2n+1}^2-F_{2n+2}F_{2n+1}-F_{2n+2}F_{2n}$$ $$=F_{2n+1}^2-F_{2n+2}F_{2n}$$ $$=(-1)(F_{2n+2}F_{2n}-F_{2n+1}^2)\quad(4)$$ Notice that going from the left hand side of $(3)$ to the right hand side of $(4)$ the the entire expression is multiplied by $-1$ and the indexes are decreased by one so this process going from $(3)$ to $(4)$ can be used on $(4)$ to obtain the left hand side of $(5)$. $$=(-1)(-1)(F_{2n+1}F_{2n-1}-F_{2n}^2)=F_{2n+1}F_{2n-1}-F_{2n}^2\quad(5)$$ $$F_{2n+3}F_{2n+1}-F_{2n+2}^2=F_{2n+1}F_{2n-1}-F_{2n}^2=1$$ Thus completing the proof.

Solution 3:

quantus14 has already provided an answer showing $$z_n=F_{2n-1}^2\tag1$$

Here is another way to show $(1)$.

It is sufficient to prove by induction that $(1)$ where $F_n$ is the $n$-th Fibonacci number satisfying $F_{n+1}=F_n+F_{n-1}\ (n\ge 0)$ with $F_{-1}=1,F_0=0$.

$(1)$ is true for $n=0,1$ since $$z_0=1=F_{-1}^2,\qquad z_1=1=F_{1}^2$$

Supposing that $z_n=F_{2n-1}^2$ and $z_{n-1}=F_{2n-3}^2$ gives$$\begin{align}z_{n+1}&=7z_n-z_{n-1}-2 \\\\&=7F_{2n-1}^2-F_{2n-3}^2-2 \\\\&=7(F_{2n+1}-F_{2n})^2-F_{2n-3}^2-2 \\\\&=F_{2n+1}^2+6F_{2n+1}^2-14F_{2n}F_{2n+1}+7F_{2n}^2-(2F_{2n+1}-3F_{2n})^2 \\&\qquad +2(F_{2n}F_{2n+1}+F_{2n}^2-F_{2n+1}^2) \\\\&=F_{2n+1}^2\qquad\square\end{align}$$ where $$F_{2n}F_{2n+1}+F_{2n}^2-F_{2n+1}^2=-1\tag2$$was used.

Finally, let us prove $(2)$ by induction.

$(2)$ is true for $n=0$ since $$F_{0}F_{1}+F_{0}^2-F_{1}^2=0+0-1=-1$$

Supposing that $(2)$ is true for $n$ gives $$\begin{align}-1&=F_{2n}F_{2n+1}+F_{2n}^2-F_{2n+1}^2 \\\\&=(F_{2n+2}-F_{2n+1})(F_{2n+3}-F_{2n+2})+(F_{2n+2}-F_{2n+1})^2 \\&\qquad -(F_{2n+3}-F_{2n+2})^2 \\\\&=(F_{2n+2}F_{2n+3}+F_{2n+2}^2-F_{2n+3}^2)-F_{2n+2}^2-F_{2n+1}F_{2n+3} \\&\qquad +F_{2n+1}F_{2n+2}-2F_{2n+2}F_{2n+1}+F_{2n+1}^2-F_{2n+2}^2 \\&\qquad +2F_{2n+3}F_{2n+2} \\\\&=(F_{2n+2}F_{2n+3}+F_{2n+2}^2-F_{2n+3}^2)-2F_{2n+2}^2-F_{2n+1}F_{2n+3} \\&\qquad -F_{2n+2}F_{2n+1}+F_{2n+1}^2+2F_{2n+3}F_{2n+2} \\\\&=(F_{2n+2}F_{2n+3}+F_{2n+2}^2-F_{2n+3}^2) \\&\qquad -F_{2n+1}F_{2n+3}+F_{2n+2}F_{2n+1}+F_{2n+1}^2 \\\\&=(F_{2n+2}F_{2n+3}+F_{2n+2}^2-F_{2n+3}^2) \\&\qquad -F_{2n+1}(F_{2n+3}-F_{2n+2}-F_{2n+1}) \\\\&=F_{2n+2}F_{2n+3}+F_{2n+2}^2-F_{2n+3}^2\qquad\square\end{align}$$