1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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\,$. $\endgroup$ – dxiv Apr 19 '18 at 16:30
  • $\begingroup$ @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$? $\endgroup$ – Rodi Apr 19 '18 at 17:33
  • $\begingroup$ 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\,$. $\endgroup$ – dxiv Apr 19 '18 at 17:37
  • $\begingroup$ @dxiv you are correct, I used the wrong notation. What would my $s$ be if $F(n) = 3*n^3+3^n$ $\endgroup$ – Rodi Apr 19 '18 at 20:02
  • $\begingroup$ 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. $\endgroup$ – dxiv Apr 19 '18 at 20:06

Your Answer

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

Browse other questions tagged or ask your own question.