Solve recurrence equation

Question

Could you Show me how to solve this equation:

$$x_n = \sqrt2x_{n-1} + \sqrt3$$

for $n \ge 1$ with $x_0 = 1$.

Answer 1

Hint: find a $b\in \mathbb{R}$ such that $x_n-b=\sqrt{2}(x_{n-1}-b)$, then you get a Geometric series.

Answer 2

There are many techniques that will work. Perhaps the most elementary is simply to ‘unwind’ the recurrence. For convenience let $a=\sqrt2$ and $b=\sqrt3$. Then

$$\begin{align*} x_n&=\sqrt2 x_{n-1}+\sqrt3\\ &=ax_{n-1}+b\\ &=a(ax_{n-2}+b)+b\\ &=a^2x_{n-2}+ab+b\\ &=a^2(ax_{n-3}+b)+ab+b\\ &=a^3x_{n-3}+a^2b+ab+b\\ &\;\vdots\\ &=a^kx_{n-k}+a^{k-1}b+a^{k-2}b+\ldots+ab+b\\ &\;\vdots\\ &=a^nx_0+a^{n-1}b+a^{n-2}b+\ldots+ab+b\\ &=a^n+b\sum_{k=0}^{n-1}a^k\;. \end{align*}$$

That last summation is just a geometric series, so you can evaluate it in closed form to get an expression for $x_n$ in closed form. To finish up, you should then prove by induction on $n$ that your expression is correct: the calculation above isn’t fully rigorous. The step between the two vertical ellipses is a matter of spotting a pattern, but it doesn’t actually prove that the pattern is there.

Answer 3

A linear recurrence of the first order. Foor simplicity, call $a = \sqrt{2}$, $b = \sqrt{3}$. Then, dividing through by $a^{n + 1}$: $$ \begin{align*} x_{n + 1} - a x_n &= b \\ \frac{x_{n + 1}}{a^{n + 1}} - \frac{x_n}{a^n} &= b a^{-n} \end{align*} $$ Sum for $0 \le n < k$ to get: $$ \frac{x_k}{a^k} - x_0 = b \sum_{0 \le n < k} a^{-n} $$ The sum is geometric, finishing this off is routine.