# 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}$

• Impossible. $a_1$ is undefined since you only gave $a_0$. – user21820 Mar 23 '15 at 12:03

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.