# Algorithm for particular solution in non homogeous recurrence relation

I am currently studying discrete mathematics and my book covers a theorem for finding a particular solution. The book basically tells me to solve a non homogeneous recurrence relation in two steps. First find the solution for the associated homogeneous recurrence relation, then find the particular solution.

$$( a_n^{(h)}+ a_n^{(p)})$$

I know how to solve the associated homogeneous recurrence relation.

The next step is to solve the particular solution, for which it says the following.

Suppose that ${a_n}$ satisfies the linear nonhomogeneous recurrence relation $$a_n = c_1a_{n-1} + c_2a_{n-2} + ... + c_k a_{n-k} + F(n)$$ Where $c_1, c_2, ..., c_k$ are real numbers and $$F(n) = (b_tn^t + > b_{t-1}n^{t-1} + ... + b_1n + b_0)s^n$$ Where $b_0, b_1, ... b_t$ and $s$ are real numbers. When $s$ is not a root of the characteristic equation of the associated linear homogeneous recurrence relation, there is a particular solution of the form $$(p_tn^t + p_{t-1}n^{t-1} > + ... + p_1n + p_0)s^n$$ When $s$ is a root of the characteristic equation and its multiplicity is $m$, there is a particular solution of the form $$n^m(p_tn^t + p_{t-1}n^{t-1} + ... + p_1n + p_0)s^n$$

I do understand that I have to use a different formula depending on if my $s$ is equal to one of my roots, found when calculating the associated homogeneous recurrence relation.

What I don't quite understand is what the $s$ stands for.

Using an example $s(n) = 8*s^{n-2} - 16*s^{n-4} + n^3$ with $s(0)=0$, $s(1)=1$, $s(2)=2$, $s(2)=2$

This gives me roots $r = 2$ with multiplicity $2$ and $r = -2$ with multiplicity $2$ as well.

What would be the $s$ and why would it be the $s$? How do I determine the $s$?

Once I have determined the $s$, do I just fill in the formula and find values for $p$ to determine the entire particular solution?

If someone could elaborate on this piece of theory and explain it a bit more step by step I hope to understand this theorem better, the book kind of fails on explaining it in smaller steps.

• Using an example In that example $s=1$ since $n^3$ is not multiplied by any power of a constant. When s is not a root of the characteristic equation Take for example $\,a_n = 8 a_{n-2} - 16a_{n-4} + n^3 \cdot 3^n\,$. When s is a root of the characteristic equation Take for example $\,a_n = 8 a_{n-2} - 16a_{n-4} + n^3 \cdot 2^n\,$. – dxiv Apr 19 '18 at 16:30
• @dxiv So if I understand correctly, if the formula was $s(n) = 8*s^{n-2} - 16*s^{n-4} + 3*n^3$ the $s$ would be $3$? – Rodi Apr 19 '18 at 17:33
• the s would be 3 That's correct, but you are confusing things with the notation. Presumably, you meant to write $\,s_{n-2}\,$, not $\,s^{n-2}\,$, and that $\,s\,$ is not the same one as the other $\,s=3\,$. – dxiv Apr 19 '18 at 17:37
• @dxiv you are correct, I used the wrong notation. What would my $s$ be if $F(n) = 3*n^3+3^n$ – Rodi Apr 19 '18 at 20:02
• That $F(n)$ is not in the form quoted in the question, so there is no such $s$. What you could do in this case, instead, is find particular solutions for $F_1(n)=3n^3$ and $F_2(n)=3^n$ (which are both in the "right" form) then add them up. – dxiv Apr 19 '18 at 20:06