How can I find the sum of any homogenous linear recurrence relation? I've become interested in linear recurrence relations of the form $a_n=-a_{n-1}-a_{n-2}- ...
$ where $a_0=1$.  For the first of these relations I considered $a_n=-a_{n-1}-a_{n-2}$ where $a_0=1$ and solved to give $$a_n=\bigg(\frac12+\frac{\sqrt3i}6\bigg)\bigg(\frac{-1+\sqrt3i}{2}\bigg)^n+\bigg(\frac12-\frac{\sqrt3i}{6}\bigg)\bigg(\frac{-1-\sqrt3i}{2}\bigg)^n
$$
The equation generates the sequence $1,-1,0,1,-1,0,...$ 
My question in how, in general, would you work out the sum for equations such as this, from $n=1$ to $n=p$ ? 
Furthermore, does it only depend on the linear recurrence relation and starting term?
What would the sum be if $a_n=-a_{n-1}-a_{n-2}-a_{n-3}$
 A: Well to handle general linear recurrence relations you can use formal power series :
$$A:=\sum_{n=0}^{\infty}a_nX^n $$
Suppose you are given $a_0,...,a_{k-1}$ and you have the following recursive formula for $n\geq k$ :
$$a_n=-a_{n-1}...-a_{n-k} $$
Then you have :
$$A=a_0+a_1X+...a_{k-1}X^{k-1}+\sum_{n=k}^{\infty}a_nX^n$$
Now :
$$\sum_{n=k}^{\infty}a_nX^n=\sum_{n=k}^{\infty}(-a_{n-1}...-a_{n-k})X^n$$
$$\sum_{n=k}^{\infty}a_nX^n=-\sum_{l=1}^k\sum_{n=k}^{\infty}a_{n-l}X^n$$
$$\sum_{n=k}^{\infty}a_nX^n=-\sum_{l=1}^kX^l\sum_{n=k}^{\infty}a_{n-l}X^{n-l}$$
$$\sum_{n=k}^{\infty}a_nX^n=-\sum_{l=1}^kX^l\sum_{n=k-l}^{\infty}a_{n}X^{n}$$
$$\sum_{n=k}^{\infty}a_nX^n=-\sum_{l=1}^kX^l(A-a_0-...-a_{k-l-1}X^{k-l-1})$$
Finally :
$$A=a_0+a_1X+...a_{k-1}X^{k-1}-\sum_{l=1}^kX^l(A-a_0-...-a_{k-l-1}X^{k-l-1})$$
So you finally get that :
$$(\sum_{l=0}^kX^l)A=\sum_{l=0}^{k-1}(a_0+...+a_{k-l-1}X^{k-l-1}) $$
And using a little trick :
$$\frac{1-X^{k+1}}{1-X}A=\sum_{l=0}^{k-1}\frac{(k-l-1)(k-l)}{2}a_lX^{k-l-1}$$
$$\frac{1-X^{k+1}}{1-X}A=\sum_{l=0}^{k-1}\frac{l(l+1)}{2}a_{k-l}X^{l-1}$$
Then this express $A$ as a an element of $\mathbb{C}(X)$ to which you cann apply the decomposition into simple elements to get your answer. Notice that using the fact that roots of $X^{k+1}-1$ are of finite order, this shows that your sequence will always be periodic of period dividing $n$ (whatever might be your choice of $a_0$,...,$a_{k-1}$) which is some kind of result.
