Solve recurrence equation Could you Show me how to solve this equation:
$$x_n = \sqrt2x_{n-1} + \sqrt3$$ 
for $n \ge 1$ with $x_0 = 1$.
 A: 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.
A: 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.
A: Hint: find a $b\in \mathbb{R}$ such that $x_n-b=\sqrt{2}(x_{n-1}-b)$, then you get a Geometric series.
