About the particular solution given an homogeneous solution in a recurrence relation.

Question

If your recurrence relation's characteristic equation factorizes to

$$(x+1)(x-5)^3 = 0$$

and

1. $h(n) = 3+2n \implies f_p(n) = d_0+d_1n$
2. $h(n) = 7n+3^n \implies f_p(n) = d_0+d_1n+d_23^n$
3. $h(n) = 3n^2+5^n \implies f_p(n) = d_0+d_1n+d_2n^2+d_3n^35^n$

I understand the first one, because:

$$h(n) = 3 + 2n$$

Has one constant $3$, so the particular solution has a constant $d_0$. It also has a constant $2$ multiplied by $n$, so the particular solution should have a constant $d_1$ multiplies by $n$, so

$$f_p(n) = d_0+d_1n$$

---

But I don't get the second and third ones.

For the second one, why is there a $d_0$ there? There are no "lonely" constants in $h(n)$.

For the third, I don't get any of the results at all.

Answer 1

There is a constant in $h(n)=7n+3^n$, it is zero: $$h(n)=0+7n+3^n\ .$$ NB zero is not the same as "nothing"!

For the third case you should write out the solution of the homogeneous equation first: $$a_n=A(-1)^n+B5^n+Cn5^n+dn^25^n\ ,$$ because the characteristic equation has $5$ as a root three times. Then the $5^n$ in $h(n)$ requires a term of the form $dn^k5^n$, where $k$ is the smallest possible such that this term does not appear in $a_n$. In this case, $k=3$. The other bit comes from $$h(n)=0+0n+3n^2+5^n$$ for the same reasons as part (2).