How to solve this recurrence relation $ f(n) = \frac{10+7f(n-1)}{2+f(n-1)}$

Question

I had a problem in which I ended up getting the following recurrence relation:

$$\begin{align} &f(1) = 7\\ &f(n) = \dfrac{10+7f(n-1)}{2+f(n-1)} \end{align}$$

I haven't solved much recurrence relations, and I am unaware of any general procedure. The only thing I was able to do till now was to get this relation. I have tried putting $n$ as $n+1$, but it soon gets unsolvable.

In a more crude form, $$f(n) = 5+ \dfrac{1}{\frac{1}{f(n-1)}+\frac{1}{2}}$$

Answer 1

The solutions for $$x=\frac{10+7x}{2+x}$$ are $x=\frac{5\pm\sqrt{65}}{2}$.

Then, $$f(n)-\frac{5\pm\sqrt{65}}{2}=\frac{10+7f(n-1)}{2+f(n-1)}-\frac{5\pm\sqrt{65}}{2}=\frac{10\mp 2\sqrt{65}+(9\mp\sqrt{65})f(n-1)}{2(2+f(n-1))}$$ from which we have $$\begin{align}\frac{f(n)-(5+\sqrt{65})/2}{f(n)-(5-\sqrt{65})/2}&=\frac{{10- 2\sqrt{65}+(9-\sqrt{65})f(n-1)}}{{10+ 2\sqrt{65}+(9+\sqrt{65})f(n-1)}}\\&=\frac{9-\sqrt{65}}{9+\sqrt{65}}\cdot \frac{f(n-1)-(5+\sqrt{65})/2}{f(n-1)-(5-\sqrt{65})/2}\end{align}$$ which can be written as $$g(n)=\alpha g(n-1)$$ This is a geometric progression where $$g(n)=\frac{f(n)-(5+\sqrt{65})/2}{f(n)-(5-\sqrt{65})/2},\quad \alpha=\frac{9-\sqrt{65}}{9+\sqrt{65}}$$ Having $g(n)=\alpha^n$, we have $$\begin{align}f(n)&=\frac{(5+\sqrt{65})/2-\alpha^n\cdot(5-\sqrt{65})/2}{1-\alpha^n}\\&=\color{red}{\frac{(5+\sqrt{65})(9+\sqrt{65})^n-(5-\sqrt{65})(9-\sqrt{65})^n}{2((9+\sqrt{65})^n-(9-\sqrt{65})^n)}}\end{align}$$

Answer 2

Let we state it in a slightly different way. Let $(a_1,b_1)=(7,1)$ and: $$\begin{pmatrix} a_{n+1} \\ b_{n+1}\end{pmatrix} = \begin{pmatrix}7 & 10 \\ 1 & 2\end{pmatrix}\begin{pmatrix} a_{n} \\ b_{n}\end{pmatrix} = M \begin{pmatrix} a_{n} \\ b_{n}\end{pmatrix}.$$

The eigenvalues of $M$ are $\frac{9\pm\sqrt{65}}{2}$. By the Cayley-Hamilton theorem, the characteristic polynomial of the sequence $$ \left\{\begin{pmatrix} a_{n+1} \\ b_{n+1}\end{pmatrix}\right\}_{n\geq 1} $$ is the same as the characteristic polynomial of $M$. Component-wise, we have: $$ a_n = A_+ \left(\frac{9+\sqrt{65}}{2}\right)^n + A_- \left(\frac{9-\sqrt{65}}{2}\right)^n, $$ $$ b_n = B_+ \left(\frac{9+\sqrt{65}}{2}\right)^n + B_- \left(\frac{9-\sqrt{65}}{2}\right)^n, $$ where the constants $A_{\pm},B_{\pm}$ can be found by computing the first values of $(a_i,b_i)$, then solving a linear system. In our case $(a_1,b_1)=(7,1)$ and $(a_2,b_2)=(59,9)$ give:

$$ \frac{a_n}{b_n}=\frac{(5+\sqrt{65})(9+\sqrt{65})^n-(5-\sqrt{65})(9-\sqrt{65})^n}{2((9+\sqrt{65})^n-(9-\sqrt{65})^n)}$$

but the LHS is exactly $f(n)$. That also gives us:

$$ \lim_{n\to +\infty} f(n) = \color{red}{\frac{5+\sqrt{65}}{2}}.$$