0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ In the special case of linear recurrences with constant coefficients where the inhomogeneity is a polynomial in $n$, a particular solution is a polynomial of the same degree as the inhomogeneity. The only possible exception is if a constant is a homogeneous solution and the inhomogenity is a constant; in this case a particular solution is a polynomial of a higher degree (specifically the multiplicity of the root $0$ of the characteristic polynomial). Something similar happens when you have an exponential times a polynomial. Other cases are generally much more difficult. $\endgroup$ – Ian Jan 12 '16 at 19:36
  • $\begingroup$ @Ian I do not wish to appear ungrateful or rude, as I appreciate the response, but that is exactly the type of explanation I simply do not understand. Are you saying that if the non-homogeneous part looks like $n^k$ in the recurrence relation, then the closed-form will have solution also of form $n^k$? But you're saying this is not the case if a constant is a solution, which I don't know how to check or what that really means, let alone the rest of the comment. I need hard examples that show these various cases so I can understand what is being said. $\endgroup$ – AJJ Jan 12 '16 at 19:40
  • $\begingroup$ If the non-homogeneous part is a polynomial of degree $k$, then a particular solution is generally some other polynomial of degree $k$, which you can find by assuming it is the form $a_0 + a_1 n + \dots + a_k n^k$ and solving for the coefficients. You can have an exception to this rule if $1$ is a characteristic polynomial; in this case you can wind up needing a polynomial of a higher degree. An example: $x_n + 2 x_{n-1} + x_{n-2} = n$, assume the solution is of the form $x_n = an+b$, then you must have $an+b + 2a(n-1) + 2b + a(n-2) + b = n$. Simplify to $4an+4b-3a=n$, so $4b-3a=0,4a=1$. $\endgroup$ – Ian Jan 12 '16 at 19:42
  • $\begingroup$ The idea behind this is that if you plug a polynomial into the recurrence, you get back a polynomial of the same or smaller degree. The same thing happens in linear ODEs with constant coefficients. $\endgroup$ – Ian Jan 12 '16 at 19:46
  • $\begingroup$ " You can have an exception to this rule if 1 is a characteristic polynomial" by this do you refer explicitly to the homogeneous recurrence? When would the characteristic polynomial ever be simply 1? For $T(n) = 2T(n-1)$ which is the lowest recurrence I can make (degree $1$) it still has an $x$ term: $x-2$. Also what is $x_n + 2x_{n-1} + x_{n-2} = n$ referring to? $\endgroup$ – AJJ Jan 12 '16 at 19:48
0
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ "An exception occurs when 1 is a root of the characteristic polynomial" Could I also arrive at this result by modeling the homogeneous part $x^n = 3n^{n-1} + 2x^{n-2}$ which can be divided by $x^{n-2}$ and rearranged to get $x^2 - 3x + 2 = 0$ which is $(x-2)(x-1) = 0$ which has a root of $1$? Is this solution of $1$ the only time this exception occurs? Otherwise I can always assume the solution has the same degree? $\endgroup$ – AJJ Jan 12 '16 at 20:48
  • $\begingroup$ Also when you say "try it with a higher degree" is there any reason you aren't trying $an^2 + bn + c$ as opposed to $an^2 + bn$? $\endgroup$ – AJJ Jan 12 '16 at 20:49
  • $\begingroup$ @ArukaJ First question: in the case of a polynomial inhomogeneity, this is the only exception. More exceptions (of this same general character) occur with exponential inhomogeneities. Other inhomogeneities typically require completely different methods. Second question: when $1$ is a root of the characteristic polynomial of multiplicity $m$, all polynomials of degree at most $m$ are mapped to zero by the corresponding linear map. Thus they will be absorbed into the homogeneous solution, and so they needn't be included in the search for the particular solution. $\endgroup$ – Ian Jan 12 '16 at 20:50
  • $\begingroup$ Let $d$ be the degree of the non-homogeneous polynomial of the recurrence. Then is it safe to say that the degree of the solution (for the non-homogeneous part) is degree $d + k$ where $k$ is the multiplicity of the root of $1$ in the characteristic polynomial of the homogeneous part of the recurrence? $\endgroup$ – AJJ Jan 12 '16 at 20:51
  • $\begingroup$ @ArukaJ Yes, that's correct, at least in general. It's possible for it to have lower degree, if you choose the inhomogeneity just right. $\endgroup$ – Ian Jan 12 '16 at 20:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.