With the help of you guys I've been able to learn how to solve various recurrence equations, but today I came across one I couldn't handle:
Find a closed form of the sequence $\{x_n\}$ of recurrence relation (where $n \in \mathbb N$): $$ \begin{cases} x_1 = a > 0\\x_{n+1} = \dfrac{1}{1+x_n}\end{cases} $$
I've already made several attempts which include:
- Trying to infer the pattern by expanding the continuous fraction from bottom up. No result
- Expressing $x_{n+2}$ and multiply/add/subtract/divide expressions for $x_{n+1}$ and $x_{n+2}$. No result
- Suppose that $x_{n}$ has a rational form $k_n \over p_n$ and playing with the equations in different ways. No result
I believe there should be some clever trick to untangle this, but apparently i'm too dumb to see it.
The answer is known to be a fraction involving the Golden Ratio $\frac{\sqrt5 - 1}{2}$ so maybe this may help.
Update
Using @AnotherJohnDoe's hint we may perform the following transformation:
Let $x_n = \frac{t_n}{t_{n+1}}$, then:
$$ \frac{t_{n+1}}{t_{n+2}} = \frac{1}{1+\frac{t_n}{t_{n+1}}} = \frac{t_{n+1}}{t_n + t_{n+1}} $$
Which defines a recurrence relation in terms of $t$:
$$ t_{n+2} - t_{n+1} - t_n = 0 $$
The characteristic equation for this recurrence has two root so the closed form of $\{t_n\}$ is:
$$ t_n = C_1\cdot\left({1+\sqrt5\over 2}\right)^n + C_2 \cdot \left({1-\sqrt5 \over 2}\right)^n $$
Let $\phi_1 = \frac{1+\sqrt5}{2}$ and $\phi_2 = \frac{1-\sqrt5}{2}$:
$$ t_n = C_1\cdot \phi_1^n + C_2\cdot\phi_2^n \\ t_{n+1} = C_1\cdot \phi_1^{n+1} + C_2\cdot\phi_2^{n+1} $$
Then:
$$ x_n = \frac{t_n}{t_{n+1}} \\ x_n = \frac{C_1\cdot \phi_1^n + C_2\cdot\phi_2^n}{C_1\cdot \phi_1^{n+1} + C_2\cdot\phi_2^{n+1}} $$
So using the initial conditions $x_1 = a$ and $x_2 = {1\over 1+a}$:
$$ \begin{align} a &= \frac{C_1\cdot \phi_1 + C_2\cdot\phi_2}{C_1\cdot \phi_1^2 + C_2\cdot\phi_2^2} \\ {1\over 1+a} &= \frac{C_1\cdot \phi_1^2 + C_2\cdot\phi_2^2}{C_1\cdot \phi_1^3 + C_2\cdot\phi_2^3} \end{align} $$
But this system doesn't seem to have solutions.
When stuck, there's always the option of computing the first few terms of the sequence, to see if a pattern appears.
Computing the first $6$ terms, we get \begin{align*} x_1&=a\\[4pt] x_2&=\frac{1}{1+a}\\[4pt] x_3&=\frac{1+a}{2+a}\\[4pt] x_4&=\frac{2+a}{3+2a}\\[4pt] x_5&=\frac{3+2a}{5+3a}\\[4pt] x_6&=\frac{5+3a}{8+5a}\\[4pt] \end{align*} so it appears to be the case that $$x_n=\frac{F_{n-1}+aF_{n-2}}{F_n+aF_{n-1}}$$ where $F_n$ is the $n$-th Fibonacci number (using $F_{-1}=1$ and $F_{0}=0$).
The proof by induction is straightforward . . .
For $n=1$, we have $$\frac{F_0+aF_{-1}}{F_1+aF_0}=\frac{a}{1}=a=x_1$$ so the base case is verified.
Suppose the claim holds for some positive integer $n$.$\;$Then \begin{align*} x_{n+1}&=\frac{1}{1+x_n}\\[4pt] &=\frac{1}{1+{\Large{\frac{F_{n-1}+aF_{n-2}}{F_n+aF_{n-1}}}}}\\[4pt] &=\frac{F_n+aF_{n-1}}{(F_{n-1}+F_n)+a(F_{n-2}+F_{n-1})}\\[4pt] &=\frac{F_n+aF_{n-1}}{F_{n+1}+aF_n}\\[4pt] \end{align*} which completes the induction.