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

-

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

-
I don't get your third equation, how did you get it? Even though I plus one'd your answer! –  Gigili Jun 6 '12 at 15:21
@Gigili - I added a clarification. Does it help? –  Ayman Hourieh Jun 6 '12 at 15:48
Yes, thank you. –  Gigili Jun 6 '12 at 17:13
Hi Ayman, I like this approach.I am working on deriving closed form for fibonacci series in the same way, can you please guide me. –  Rajesh Jul 20 '14 at 13:45

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_r$ and let $t_1,...,t_r$ be all its 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 its 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$

-
is that suppose to be $\beta_1, ..., \beta_s$ instead of $b_s$? –  user31280 Nov 13 '12 at 1:53
@F'Ola Yinka: indeed. –  Dennis Gulko Nov 13 '12 at 7:30

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.

-

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

-