How do we deal with recurrence relation characteristic equations that are not quadratic or have imaginary roots? 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?

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.
