<s>[INST] How to find the closed form formula for this recurrence relation $ x_{0} = 5 $
$ x_{n} = 2x_{n-1} + 9(5^{n-1})$
I have computed: $x_{0} = 5, x_{1} = 19, x_{2} = 83, x_{3} = 391, x_{4} = 1907$, but cannot see any pattern for the general $n^{th}$ term.
 [/INST] Note that Ayman’s technique of ‘unwinding’ the recurrence works even without the preliminary division by $2^n$:
$$\begin{align*}
x_n&=2x_{n-1}+9\cdot5^{n-1}\\
&=2\left(2x_{n-2}+9\cdot5^{n-2}\right)+9\cdot5^{n-1}\\
&=2^2x_{n-2}+2\cdot9\cdot5^{n-2}+9\cdot5^{n-1}\\
&=2^2\left(2x_{n-3}+9\cdot5^{n-3}\right)+2\cdot9\cdot5^{n-2}+9\cdot5^{n-1}\\
&=2^3x_{n-3}+2^2\cdot9\cdot5^{n-3}+2\cdot9\cdot5^{n-2}+9\cdot5^{n-1}\\
&\qquad\qquad\qquad\vdots\\
&=2^kx_{n-k}+2^{k-1}\cdot9\cdot5^{n-k}+2^{k-2}\cdot9\cdot5^{n-k+1}+\ldots+9\cdot5^{n-1}\\
&=2^kx_{n-k}+9\sum_{i=0}^{k-1}2^i5^{n-1-i}\\
&\qquad\qquad\qquad\vdots\\
&=2^nx_0+9\sum_{i=0}^{n-1}2^i5^{n-1-i}\\
&=5\cdot2^n+9\sum_{i=0}^{n-1}\left(\frac25\right)^i5^{n-1}\\
&=5\cdot2^n+9\cdot5^{n-1}\left(\frac{1-(2/5)^n}{1-2/5}\right)\\
&=5\cdot2^n+3\cdot5^n\left(1-\frac{2^n}{5^n}\right)\\
&=5\cdot2^n+3\cdot5^n-3\cdot2^n\\
&=2^{n+1}+3\cdot5^n\;.
\end{align*}$$
</s>