8
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @AymanHourieh, why did you choose $2^{n}$? Thanks. $\endgroup$ – InfZero Sep 3 '16 at 17:41
7
$\begingroup$

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$

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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