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.
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)