Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

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

share|improve this answer
    
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 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_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$

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.