# Thread: Simple recurrence relations question

1. ## Simple recurrence relations question

Hello,
I have two textbook examples of simple non-homogeneous recurrences with model solutions, but there's one thing that I don't understand in both of them.

First recurrence: $\displaystyle u_0=3, \ u_1=20$
$\displaystyle u_n=4u_{n-1}-4u_{n-2}-6n+1, \ n \geq 2$

Characteristic equation ($\displaystyle x^2-4x+4=0$) has double characteristic root 2.

Non-homogeneous part is first degree polynomial, so the guess is $\displaystyle p(n)=an+b$. Then we substitute it to original recurrence and get following equation:
$\displaystyle an+b=4(a(n-1)+b)-4(a(n-2)+b)-6n+1=-6n+4a+1$

Now comes the part, that I don't understand. Textbook says, that we get two solutions ($\displaystyle a=-6$ and $\displaystyle b=-23$) from that equation. But it completely baffles me, how I'am supposed to get those solutions. I think it have something to do with method of undetermined coefficients, but we haven't got taught anything about it, gg. Rest of the solution I understand.

Second recurrence: $\displaystyle a_n=a_{n-1}+a_{n-2}+2n$ (no other information given)

Guess is form $\displaystyle p(n)=bn+c$. And subtitution to recurrence:
$\displaystyle bn+c=(b(n-1)+c)+(b(n-2)+c)+2n \Leftrightarrow -bn+(3b-c)=2n$

Now I don't understand even, how that right side of biconditional is got.
When I reduce that equation, I get something like: $\displaystyle 2bn-3b+2c+2n$. Again equation is "solved" and $\displaystyle b=-2$ and $\displaystyle c=-6$ is got, which I don't understand at all.

So, any help is appreciated. Thank you!

2. Originally Posted by Greg98
Hello,
I have two textbook examples of simple non-homogeneous recurrences with model solutions, but there's one thing that I don't understand in both of them.

First recurrence: $\displaystyle u_0=3, \ u_1=20$
$\displaystyle u_n=4u_{n-1}-4u_{n-2}-6n+1, \ n \geq 2$

Characteristic equation ($\displaystyle x^2-4x+4=0$) has double characteristic root 2.

Non-homogeneous part is first degree polynomial, so the guess is $\displaystyle p(n)=an+b$. Then we substitute it to original recurrence and get following equation:
$\displaystyle an+b=4(a(n-1)+b)-4(a(n-2)+b)-6n+1=-6n+4a+1$

Now comes the part, that I don't understand. Textbook says, that we get two solutions ($\displaystyle a=-6$ and $\displaystyle b=-23$) from that equation. But it completely baffles me, how I'am supposed to get those solutions. I think it have something to do with method of undetermined coefficients, but we haven't got taught anything about it, gg. Rest of the solution I understand.

Second recurrence: $\displaystyle a_n=a_{n-1}+a_{n-2}+2n$ (no other information given)

Guess is form $\displaystyle p(n)=bn+c$. And subtitution to recurrence:
$\displaystyle bn+c=(b(n-1)+c)+(b(n-2)+c)+2n \Leftrightarrow -bn+(3b-c)=2n$

Now I don't understand even, how that right side of biconditional is got.
When I reduce that equation, I get something like: $\displaystyle 2bn-3b+2c+2n$. Again equation is "solved" and $\displaystyle b=-2$ and $\displaystyle c=-6$ is got, which I don't understand at all.

So, any help is appreciated. Thank you!
Your form of the particular solution is correct.

$\displaystyle p(n)=an+b$ Now we just plug this into the equation below

$\displaystyle u_n-4u_{n-1}+4u_{n-2}=-6n+1$ This gives

$\displaystyle an+b-4[a(n-1)+b]+4[a(n-2)+b]=-6n+1$ Now expand the left hand side to get

$\displaystyle an+b-4an+4a-4b+4an-8a+4b=-6n+1$ simplifying gives

$\displaystyle an-4a+b=-6n+1$ Now for this to be true the coefficients must be equal and satisfy this system of equation

$\displaystyle \begin{array}{c c c } a &+0b &=-6 \\ -4a & +b & =1\end{array}$

This gives that values of a and b

Try the 2nd one again (using what I did above) and note that this may be helpful

$\displaystyle a_n-a_{n-1}-a_{n-2}=2n+0$

3. That was great clarification - just what I was looking for. This problem has been puzzling me for long, though I managed to pass the course with a decent grade. Huge thanks to you!!!