Suppose we have $$H(n) = H(n-1)-H(n-2) \rightarrow x^2-x+1 \rightarrow r_1 = \frac{1+\sqrt{-3}}{2}, r_2 = \frac{1-\sqrt{-3}}{2}$$
or
$$H(n) = H(n-1)+H(n-2)+H(n-3) \rightarrow x^3-x^2-x-1=0$$
In either case, how would the recurrence relation be solved? Are there other techniques for complex roots/non-quadratics?
On
If the characteristic polynomial has distinct roots $r_1,r_2,\dots,r_m$ then the general solution of the recurrence is $H(n)=a_1r_1^n+a_2r_2^n+\cdots+a_mr_m^n$. Actually finding the roots $r_1,r_2,\dots,r_m$ may be difficult/impossible if $m\ge3$, but if you can find those roots the formula holds.
On
From my experience, there are two directions to approaching recursive equations. The first direction is from a pure-math perspective. If we approach from this angle, it is usually sufficient to compute the form of a solution, possibly in an abstract manner. In this case, once we have reduced to finding roots of polynomials, we are done - everything has been described.
The other direction is from a computer science or applied math perspective. Oftentimes, we want to make numerical statements about the growth rate of the sequence, to a fairly high degree of precision. From this perspective, things are even simpler. Once you have obtained the characteristic equation, simply approximate the root of largest magnitude. Then you can approximate the sequence by a geometric series in the largest root.
The situation is pretty concrete in either case, in my opinion. Decide which direction you are actually interested in, and then apply the corresponding techniques.
On
There are some efficient techniques for tackling recurrence relations such as generating function technique and some transform techniques such as the Z-transform technique.
On
The first one repeats $$ a,b,b-a,-a,-b,a-b, a,b,b-a,-a,-b,a-b, a,b,b-a,-a,-b,a-b, a,b,c,-a,-b,a-b,\ldots $$
This does follow, eventually, from the description $$ H(n) = A \, r_1^n + B \, r_2^n $$ for some complex constants $A,B.$
Indeed, $$ \left( \begin{array}{r} A \\ B \end{array} \right) = \left( \begin{array}{rr} \frac{1}{2} - \frac{i}{2 \sqrt 3} & -\frac{1}{2} - \frac{i}{2 \sqrt 3} \\ \frac{1}{2} + \frac{i}{2 \sqrt 3} & -\frac{1}{2} + \frac{i}{2 \sqrt 3} \end{array} \right) \cdot \left( \begin{array}{r} a \\ b \end{array} \right) $$
So, for the sequence $$ 1,-1,-2,-1,1,2, 1,-1,-2,-1,1,2,\ldots $$ we have $a=1,b=-1,$ then $A=1,B=1$ and $$ H(n) = r_1^n + r_2^n. $$
For the sequence $$ 1,1,0,-1,-1,0, 1,1,0,-1,-1,0,\ldots $$ we have $a=1,b=1,$ then $A=- \frac{i}{ \sqrt 3} ,B= \frac{i}{ \sqrt 3}$ and $$ H(n) = - \frac{i}{ \sqrt 3} \left( r_1^n - r_2^n \right). $$
The repetition of length 6 and the half-repetition with negation of length 3 can be seen from both roots satisfying $r_j^6 = 1$ and $r_j^3 = -1.$ Or, you can just start a sequence with symbols $a,b$ and confirm the pattern I gave first.
If you apply the techiques applicable to quadratics/real roots with complex numbers, you'll see that at the end you have pairs of conjugate complex numbers that add up to reals. Just that the solutions aren't monotonic, they fluctuate.
Just take a look at what happens if you end up with $A(z) = \frac{1}{1 + z + z^2}$.