How to find the closed form formula for this recurrence relation

Question

$ 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.

Answer 1

If you're not familiar with the method that Phira explained, divide both sides by $2^n$:

$$ \dfrac{x_{n}}{2^n} = \dfrac{x_{n-1}}{2^{n-1}} + \dfrac{9}{2}\left(\dfrac{5}{2}\right)^{n-1} $$

Call $\dfrac{x_{n}}{2^n} = s_n$:

$$ s_n = s_{n-1} + \dfrac{9}{2}\left(\dfrac{5}{2}\right)^{n-1} $$

If we keep expanding $s_{n-1}$ in the RHS recursively, we get:

$$ s_n = s_0 + \dfrac{9}{2}\left(\dfrac{5}{2}\right)^{0} + \dfrac{9}{2}\left(\dfrac{5}{2}\right)^{1} \cdots + \dfrac{9}{2}\left(\dfrac{5}{2}\right)^{n-2} + \dfrac{9}{2}\left(\dfrac{5}{2}\right)^{n-1} $$

Where $s_0 = \dfrac{x_0}{2^0} = x_0$.

This means that:

$$ s_n = x_0 + \sum_{k=1}^{n}\dfrac{9}{2}\left(\dfrac{5}{2}\right)^{k-1} $$

This is a geometric series:

$$ s_n = 3 \left(\dfrac{5}{2}\right)^n + 2 $$

And therefore:

$$ x_n = 3 \cdot 5^n + 2 \cdot 2^n $$

Answer 2

Elaborating on Phira's answer: In general, for a given recurrence relation of the form $x_n+a_1x_{n-1}+...+a_{r}x_{n-r}=k^nf(n)$, where $a_1,...,a_r,k$ are given constants and $f(n)$ is a polynomial in $n$, and assuming you are given $x_0,...,x_{r-1}$, then you can solve this in two steps:
Step 1: define the characteristic polynomial to be $t^r+a_1t^{r-1}+...+a_0$. Let $t_1,...,t_r$ be all the roots (over $\mathbb{C}$). If they are all distinct, then you write $x_n^{(h)}=\alpha_1t_1^n+...+\alpha_rt_r^n$ - the homogeneous part. If you have multiplicity $s$ to some root $t_j$ then you replace it's appearances in the solution with $(n^{s-1}\beta_1+...+\beta_{s})t_j^n$.
Step 2: $x_n^{(p)}=k^nn^sg(n)$ where $k$ is the same, $s$ is the multiplicity of $k$ as a root of the characteristic polynomial defined above (if $k$ is not a root, then $s=0$) and $g(n)$ is a polynomial of the same degree as $f(n)$.
Now $x_n=x_n^{(h)}+x_n^{(p)}$. Substituting back and using the given $x_0,...,x_{r-1}$ you can find the constants.

Now, apply this method to your problem: the characteristic polynomial will be $t-2$. Hence $x_n^{(h)}=\alpha 2^n$
$k=5$, $f(n)=\frac{9}{5}$. Since $k=5$ is not a root of the characteristic polynomial, you have $x_n^{(p)}=5^n\beta$, since $g(n)$ is a polynomial of the same degree as $f(n)$, i.e. constant.
Hence you have $x_n=2^n\alpha+5^n\beta$. Plugging it in the first equation gives you $$2^n\alpha+5^n\beta=2\cdot2^{n-1}\alpha+2\cdot5^{n-1}\beta+9\cdot5^{n-1}$$ So $(5\beta-2\beta)5^{n-1}=9\cdot5^{n-1}$. Hence $\beta=3$.
Now plug-in $5=x_0=\alpha+\beta$. So $\alpha=5-\beta=2$.
Finally, $x_n=2\cdot2^n+3\cdot5^n$

Answer 3

From the general theory, you can tell immediately that $x_n=A\cdot 2^n+B\cdot 5^n$ for some constants $A$ and $B$.

Now, you can proceed to calculate the constants $A$ and $B$ using your values for $n=0$ and $n=1$.

---

If it isn't a practice exercice to understand recurrences and you really just need the result, then Wolfram alpha will give satisfaction, too: See here.

Answer 4

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*}$$