0
$\begingroup$

Usually an homogeneous linear recurrence relation of degree $k$ with $k \in\mathbb{Z}$ of the form

$$u_n = c_1u_{n-1} + c_2u_{n-2} + c_3u_{n-3} + \ldots + c_ku_{n-k}$$

has the characteristic polynomial equation of degree $k$ where each $x$-variable is raised to the power of the corresponding rank assuming $n=k$

$$x^k = c_1x^{k-1} + c_2x^{k-2} + c_3x^{k-3} + \ldots + c_{k-1}x^1 + c_kx^0$$

We know a linear recurrence relation is called non-homogeneous if it is in the form

$$u_n = c_1u_{n-1} + c_2u_{n-2} + c_3u_{n-3} + \ldots + c_ku_{n-k} + f \left(n \right)\quad\text{where}\quad f \left(n \right)\neq 0$$

The solution $\left(a_n \right)$ of a non-homogeneous recurrence relation has two parts.

First part is the solution $\left(a_h \right)$ of the associated homogeneous recurrence relation (obtained by removing the $f \left(n \right)$-part) and the second part is the particular solution $\left(a_t \right)$.

The final solution then have this form

$$a_n = a_h + a_t$$

The solution $\left(a_h \right)$ is determined by solving the characteristic polynomial equation, but what about the particular solution $\left(a_t \right)$?

I am trying to solve the following sequence $\begin{cases} u_0 &= 1 \\ u_n &= 1.5u_{n-1} + 2n \end{cases}$

$\endgroup$
1
$\begingroup$

Sketch (for a solution that does everything at once):

Consider

$$u_n=1.5u_{n-1}+2n$$ and $$ u_{n-1}=1.5u_{n-2}+2(n-1). $$

Subtracting these from each other gives $$ u_n-u_{n-1}=1.5u_{n-1}-1.5u_{n-2}+2 $$ or that $$ u_n=2.5u_{n-1}-1.5u_{n-2}+2 $$

Therefore, $$ u_{n-1}=2.5u_{n-2}-1.5u_{n-3}+2. $$

Subtracting these two gives \begin{align*} u_n-u_{n-1}&=(2.5u_{n-1}-1.5u_{n-2}+2)-(2.5u_{n-2}-1.5u_{n-3}+2)\\ &=2.5u_{n-1}-4u_{n-2}+1.5u_{n-3} \end{align*} or that $$ u_n=3.5u_{n-1}-4u_{n-2}+1.5u_{n-3}. $$

This last equation can be solved using the standard homogeneous recurrence formula.

The characteristic polynomial is then $$ x^3-3.5x^2+4x-1.5=(x-1)^2\left(x-1.5\right). $$ Therefore, the general form for $u_n$ is $$ u_n=c_1(1)^n+c_2n(1)^n+c_3(1.5)^n=c_1+c_2n+c_3(1.5)^n, $$ where the constants $c_1$, $c_2$, and $c_3$ are to be determined.

Plugging into the first recurrence, we have $$ c_1+c_2n+c_3(1.5)^n=1.5(c_1+c_2(n-1)+c_3(1.5)^{n-1})+2n $$ or that $$ c_1+c_2n=1.5c_1+1.5c_2n-1.5c_2+2n. $$ Since this equation must be true for any $n$, the corresponding coefficients must be equal. In other words, the coefficients without $n$'s satisfy $$ c_1=1.5c_1-1.5c_2 $$ and the coefficients with $n$ satisfy $$ c_2=1.5c_2+2. $$ In other words, $c_2=-4$ and $c_1=-12$.

Thus, the solution is of the form $$ u_n=-12-4n+c_3(1.5)^n. $$ Finally, using the initial value, $$ u_0=1=-12+c_3 $$ gives $$ c_3=13. $$

Putting this all together, the solution to the recurrence is $$ u_n=-12-4n+13(1.5)^n. $$

The homogeneous and particular setup here is a little complicated to express, the $(1.5)^n$ would be a solution to the homogeneous (with the initial condition $u_0=1$) and $-12-4n+12(1.5)^n$ is a solution to the particular with $u_0=0$). If you want to use the homogeneous and particular setup, you must be careful about the initial conditions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice answer. Thank you. The idea is to get rid of the particular part to get the homogeneous polynomial equation. $\endgroup$ – eigenslacker Jan 4 at 21:31
  • $\begingroup$ Can the same be applied in a generalized way to arithmetico-geometric sequences such as $u_n=1.5u_{n-1}+1$ with the initial condition $u_0=1$? $\endgroup$ – eigenslacker Jan 4 at 21:33
  • $\begingroup$ I ask this because some books usually solve for $\alpha=1.5\alpha+1$ and construct an auxiliary sequence $v_n=u_n-\alpha$ $\endgroup$ – eigenslacker Jan 4 at 21:36
  • $\begingroup$ Sure, it can be used in general (at least when $f(n)$ is a polynomial in $n$). You'll need to change the step where you determine the constants as appropriate. $\endgroup$ – Michael Burr Jan 4 at 21:36
  • 1
    $\begingroup$ Yes, when $f(n)$ is a polynomial, then the characteristic equation that you'll get using this method will be the characteristic equation of the homogeneous system times $(x-1)^{\deg(f)}$. So, it is solving the characteristic polynomial equation of degree $1$ in disguise - this can allow you to skip right to the answer and general form. $\endgroup$ – Michael Burr Jan 4 at 21:40
0
$\begingroup$

Hint:

Obviously the homogeneous solution is of the form $c\,1.5^n$. Then we can look for a particular solution with a linear form $an+b$.

We have

$$an+b=1.5(a(n-1)+b)+2n$$

and by identification we obtain $a$ and $b$.

$-4n-12$.

| cite | improve this answer | |
$\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.