Define a sequence of integers $H(n)$ by $H(0) = 1$, $H(1) = 3$ and $H(n+1) = H(n) + H(n-1)$?

Question

Then show that $H(n)$ can be expressed in the form $a\cdot(\psi(1))^n + b\cdot(\psi(2))^n$ and that $\psi(1)$ and $\psi(2)$ are the same numbers that occur in the proof of the Fibonacci numbers.

I'm quite lost with this question.

Answer 1

Write the following (this is a useful general method to solve linear recurrence relations, likely not to be the most concise in this particular case): $$ \begin{align*} H_{n} &= H_n \\ H_{n+1} &= H_{n}+H_{n-1} \end{align*} $$ or, in matrix form for $X_n\stackrel{\rm{}def}{=} \begin{pmatrix} H_n \\ H_{n+1}\end{pmatrix}$, $$ \begin{align*} X_n = \begin{pmatrix}1 & 0 \\ 1 & 1\end{pmatrix} X_{n-1} \end{align*} $$ with $X_0 = \begin{pmatrix} 0 \\ 3\end{pmatrix}$. Writing $A\stackrel{\rm{}def}{=}\begin{pmatrix}1 & 0 \\ 1 & 1\end{pmatrix}$, observe that $X_n = A^n X_0$. If you were to diagonalize $A$ to have it of the form $$ A = P\begin{pmatrix} \psi_1 & 0 \\ 0 & \psi_2\end{pmatrix} P^{-1} $$, by canceling out the products $P^{-1}P$ you would get $$X_n = P\begin{pmatrix} \psi_1^n & 0 \\ 0 & \psi_2^n\end{pmatrix} P^{-1} X_0$$ which you can then explicitly compute to obtain your result.

Answer 2

we have $q^{n+1}=q^n+q^{n-1}$ dividing by $q^n$ we get $q=1+q^{-1}$ and we get $q^2-q-1=0$ now solve this equation for $q$