I am trying to find a way to solve non-homogeneous recurrences by solving the homogeneous and non-homogeneous parts separately. I can use generating functions for the whole thing, but I want to learn the separation method, which can often lead to a quick solution.
For example:
$T(1) = 1$
$T(n) = 2T(n - 1) + n$
The solution is $T(n) = 2^{n+1} - n - 2$. I want to be able to arrive at solutions like these by splitting up $T(n)$ into the homogeneous part, $2T(n-1)$, and the non-homogeneous part $n$.
I've seen several explanations online and on this stackexchange site, but I feel like several steps get skipped and various instructions / implied intentions are not clear to me at all.
I already know how to solve homogeneous recurrences. For example the homogeneous relationship $T(n) = 2T(n-1)$ has characteristic polynomial $x - 2$ with one root, $2$, so the solution of this piece is of form $T(n) = \alpha 2^n$.
So assuming I can get the form of the homogeneous part, how do I then solve the non-homogeneous part?
One easy case is when the recurrence is linear with constant coefficients and the inhomogeneity is a polynomial. In this case a particular solution is also a polynomial. Most of the time, it is a polynomial of the same degree as the inhomogeneity. For example:
$$T(n)=-2T(n-1)-T(n-2)+n.$$
If you assume $T(n)=an+b$ then the equation becomes
$$an+b=-2a(n-1)-2b-a(n-2)-b+n.$$
This simplifies to
$$an+b=(-3a+1)n+(4a-3b)$$
So $-3a+1=a,4a-3b=b$, which are two linear equations you can solve.
An exception occurs when $1$ is a root of the characteristic polynomial. Then the solution is still a polynomial, but of a higher degree. For example:
$$T(n)=3T(n-1)-2T(n-2)+n$$
If you try $T(n)=an+b$ you find
$$an+b=3(a(n-1)+b)-2(a(n-2)+b)+n=(a+1)n+\dots$$
and you can't have $a=a+1$. In this case a solution will be a polynomial of a higher degree. Try it with $T(n)=an^2+bn$.
The problem in this case is that the linear map $F(x_n)=x_n-3x_{n-1}+2x_{n-2}$ sends constants to zero. Thus in view of the rank theorem from linear algebra, it cannot map linear polynomials onto all linear polynomials. You need to enlarge the domain to the quadratic polynomials to hit all linear polynomials. The situation gets worse still when $1$ is a multiple root of the characteristic polynomial. For instance, there is neither a linear nor a quadratic solution to $T(n)=2T(n-1)-T(n-2)+n$: you need a cubic solution instead.