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

  • $\begingroup$ Impossible. $a_1$ is undefined since you only gave $a_0$. $\endgroup$
    – user21820
    Mar 23, 2015 at 12:03

1 Answer 1


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 :


Now :






Finally :


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 :



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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .