Lowest bounds of Lucas Numbers

Question

I'm currently working with bounding terms of a recurrence relation and just filled out the table for $L_n < (1.7)^n$ and am asked to figure out why the number $1.7$ is so special and how I can adjust what I've already done to create the tightest bound possible. Earlier I had discovered that $(1.7)^3$ was the lowest. I know that I should be proving $L_n < b^n$ but how would I go about solving this as well as solving $b + 1 = b^2.$

Answer 1

The Lucas numbers can be proved or defined to be $$L_n=\varphi^n+(-\varphi)^{-n}$$ where $\varphi=\dfrac{\sqrt 5+1}{2}$.

This should help you find a both an upper and a lower bound. You can prove such formula by induction.

---

For a "not guessing" proof, we know that $L_0=2$ and $L_1=1$ while $L_{n+2}=L_{n+1}+L_{n}$ for $n=0,1,2,\dots$. This can be written as $$\begin{pmatrix} L_{n+2}\\L_{n+1}\end{pmatrix}=\begin{pmatrix} 1 &1\\1&0\end{pmatrix}\begin{pmatrix} L_{n+1}\\L_n\end{pmatrix}$$

It follows by repeated application of the above that

$$\begin{pmatrix} L_{n+2}\\L_{n+1}\end{pmatrix}=\begin{pmatrix} 1 &1\\1&0\end{pmatrix}^n\begin{pmatrix} L_{1}\\L_0\end{pmatrix}$$

Now, what we do is find out how to exponentiate $\begin{pmatrix} 1 &1\\1&0\end{pmatrix}$ easily. We do so by using its eigenvalues. These are the roots of $1+x-x^2=0$ which are precisely $\varphi$ and $1-\varphi=-\varphi^{-1}$.