1
$\begingroup$

I've made a few threads recently asking how to solve non-homogeneous recurrences and I think I've gotten the hang of it, but now I want to try a complicated thing like this:

$T(n) = 4T(n-1) + 2T(n-2) - 32T(n-3) + 59T(n-4) - 44T(n-5) + 12T(n-6) + 2^n + 5n^4 - 3n^3 + 2n + n \log(n)$

Where $T(0)... T(6) = 0...6$ for simplicity.

I constructed this in a very specific way.

So the homogeneous part has characteristic polynomial $x^6 - 4x^5 - 2x^4 + 32x^3 - 59x^2 + 44x - 12 = 0$ which is also $(x-2)^2 (x-1)^3 (x+3) = 0$

I assume this means the homogeneous part has solution of form:

$H(n) = \alpha_1 2^n + \alpha_2 n 2^n + \alpha_3 1^n + \alpha_4 n 1^n + \alpha_5 n^2 1^n + \alpha_6 (-3)^n$

Is this right?

Next, do I have to split up the non-homogeneous part into several pieces:

$2^n$ as its own piece

$5n^4 - 3n^3 + 2n$ as another piece

$n \log(n)$ as yet another piece?

Am I on the right track so far? My next question is how to correctly set up the "trial" equations for each piece.

$\endgroup$
1
$\begingroup$

You are on the right track, however there is an unfortunate side-effect of having $1$ as a root of the characteristic polynomial. Note that $5n^4 = 5n^4\cdot 1^n$. The invisible $1^n$ throws several people off.

For each "piece," as you say, you will need to try to find a particular solution of the same order.

For $2^n$, you would have needed to find a particular solution of the form $c_1\cdot 2^n$, however, note that there is already a term of that order from the solutions to the homogenous equation. As a result, we multiply by $n$ to make it linearly independent. But wait! There is also one of the order $n2^n$, so we have to take it yet another step. It will then be that we need to find a solution of the form $c_1\cdot n^22^n$

For $5n^4-3n^3+2n$, you would have needed to find an arbitrary polynomial of fourth degree: $d_4\cdot n^4+d_3\cdot n^3+d_2\cdot n^2+d_1\cdot n+d_0$, however, as with the case for $2^n$, we already have similarly ordered terms appearing in the homogeneous solution due to the invisible $1^n$'s appearing here. As a result, what we should really find is a solution of the form $d_4\cdot n^7+d_3\cdot n^6+d_2\cdot n^5+d_1\cdot n^4+d_0\cdot n^3$

For $n\log n$, there is fortunately no similarly ordered terms appearing in the homogeneous solution, however it is of the form $\log n$ times a polynomial so we simply search for solution of the form $\log n$ times a similarly ordered polynomial. In this case, $e_1\log n + e_2n\log n$. (caught this mistake during chatting with OP)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I put the root of $1$ in there specifically because it throws weird exception cases (and the root of $2$ to interfere with $2^n$, and so on) $\endgroup$ – AJJ Jan 13 '16 at 2:11
  • $\begingroup$ I am still a little confused about the invisible $1$s point, though. I don't understand why finding a recurrence of form $d_4\cdot n^4+d_3\cdot n^3+d_2\cdot n^2+d_1\cdot n+d_0$ is wrong. How does it interfere? Wouldn't it only interfere if the homogeneous solution somehow had, for example, a $n^4$ or a $n^3$ or a $n^2$ term or a $n$ term or a constant term? How are you defining "similarly ordered"? How is the polynomial component compared to the homogeneous component? $\endgroup$ – AJJ Jan 13 '16 at 2:20
  • 1
    $\begingroup$ @ArukaJ That's just it though, the homogeneous solution does have a constant term, an $n$ term, and an $n^2$ term. Instead of thinking of it as adding the invisible $1^n$, think of it as removing the redundant/unnecessary $1^n$. $\endgroup$ – JMoravitz Jan 13 '16 at 2:24
  • 1
    $\begingroup$ @ArukaJ As for how I would define "similarly ordered terms," I mean single terms $f(n)$ and $g(n)$ where $\lim\limits_{n\to\infty} \frac{f(n)}{g(n)}\in\Bbb R\setminus\{0\}$. For example, $2^n$ and $3\cdot 2^n$ are similarly ordered. $n^2$ and $4n^2$ are similarly ordered. $\log n$ and $n\log n$ are not. $\endgroup$ – JMoravitz Jan 13 '16 at 2:28
  • $\begingroup$ Sorry, what does $\lim\limits_{n\to\infty} \frac{f(n)}{g(n)}\in\Bbb R\setminus\{0\}$ mean exactly? At first I thought you were calling things similarly ordered if the $n$ terms cancelled out, but then this doesn't seem to be the case with the log example. $\endgroup$ – AJJ Jan 13 '16 at 2:36

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.