1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.