Generalized geometric series with long range dependence

Question

It is well-known the recursive relation for geometric series is $$a_n=q a_{n-1}.$$ Let $a_1>0$, $\lim_{n\to\infty}a_n<\infty$ iff $q<1$. (We always assume $q>0$. )

Consider the following generalization: $$a_n=q a_{n-1}+ q^2 a_{n-2}.$$ According to Mathematica, the general formula is $$a_n=C_1 \left[q\left(\frac{1+\sqrt{5}}{2}\right)\right]^n +C_2 \left[q\left(\frac{1-\sqrt{5}}{2}\right)\right]^n.$$ First of all, I don't really have an intuition on why the golden ratio enters the formula (except when $q=1$ we have Fibonacci). Second, it is clear whether $\lim_{n\to\infty}a_n$ is finite is no longer determined by $q<1$. In fact, $q$ needs to be much smaller in order to ensure the convergence. Let $a_0=0$ and $a_1>0$, $\lim_{n\to\infty}a_n<\infty$ iff $q<\frac{\sqrt{5}-1}{2}$. Again, I don't really understand this result.

We can further iterate this process and consider the following generalization: $$a_n=\sum_{i=0}^{n-1} q^{n-i} a_i.$$ Let $a_0=0$ and $a_1>0$. By performing numerical simulation, I find $a_n$ still has an exponential form. $\lim_{n\to\infty}a_n<\infty$ iff $q<1/2$. Has this series been studied before and how to prove the above result?

Answer 1

Notice that if we let $\, a_n := q^n b_n\,$ then $\,a_{n-k} = q^{n-k}b_{n-k}\,$ and also $\,q^k a_{n-k} = q^n b_{n-k}.\,$ This implies that $\, a_n=q a_{n-1}+ q^2 a_{n-2}\,$ becomes $\,q^nb_n = q^nb_{n-1} +q^nb_{n-2}\,$ and dividing by the common factor $\,q^n\,$ gives us $\, b_n = b_{n-1} +b_{n-2}\,$ which is the Fibonacci sequence $\,F_n\,$ recursion. The growth rate of $\,F_n\,$ is $\, F_n \sim \frac1{\sqrt{5}}\phi^n\,$ similar to a geometric series. This implies that $\,a_n \to \frac{a_1}{\sqrt{5}} \,$ if $\, q = \frac1{\phi}\,$ and $\,a_n \to 0\,$ if $\,|q| < \frac1{\phi}\,.$

Similarly for any generalization such as the one you proposed. In that case, the recursion is $\,b_n = \sum_{i=0}^{n-1} b_i\,$ whose solution is a multiple of the OEIS sequence A011782 which implies that $\,b_n = 2^{n-2}b_1\,$ if $n>1$ and $\,a_n = (2q)^{n-1}a_1\,$ if $\,n>1.\,$ This explains why the limit of $\,a_n\,$ is $\,a_1\,$ if $\,q=\frac12\,$ and $0$ if $\,|q|<\frac12.$

Answer 2

A sequence $(a_n)$ that satisfies $$a_n = qa_{n-1} + q^2a_{n-2}$$

has the following closed form : $a_n = C_1 r_1^n + C_2 r_2^n$, where $C_1, C_2$ are constants that depends on the two first terms $a_0$ and $a_1$, and $r_1$ and $r_2$ are the roots of the polynomial $X^2-qX-q^2$. Here, the roots are $q \phi$ and $q \overline{\phi}$ where $\phi$ is the golden ratio and $\overline{\phi}$ its conjugate.

Answer 3

Start with the ansatz $a_n=r^n$ first, which will provide you a class of root solutions whose linear combinations span the space of solutions. To find them, substitute the solution into the recurrence equation. Say more generally, we have

$$ a_n=A a_{n-1}+B a_{n-2} $$

Substituting $a_n=r^n$ gives

$$ a_n=r^n=A r^{n-1}+B^{n-2}r^{n-2} $$

Dive both sides by $r^{n-2}$ and bring to the quadratic normal form, which yields

$$ r^2-Ar-B=0 $$ Its canonic root solutions are $$ r_{1,2}=\frac{A}{2}\pm \sqrt{\frac{A^2}{4}+B}. $$

In your case, we have $A=q$ and $B=q^2$, which yields

\begin{align} r_{1,2}&=q \left(\frac{1}{2}\pm \frac{\sqrt{5}}{2}\right)\\ &=q\left(\frac{1\pm\sqrt{5}}{2}\right) \end{align}

Now, we can build up all possible solutions by linear combinations of the powers of the roots, i.e.

$$ a_n=C_1 \biggl(q\left(\frac{1+\sqrt{5}}{2}\right)\biggr)^n+C_2 \biggl(q\left(\frac{1-\sqrt{5}}{2}\right)\biggr)^n $$

Answer 4

Without going into linear algebra too much, the key concept is that anything of this type can be reduced to a recurrence relation of length $1$. Let's see how this would work here.

We have

$$a_n = q a_{n-1} + q^2 a_{n-2}= q (a_{n-1} + q (a_{n-2}).$$

Let's introduce a new sequence $b_n = a_n + c a_{n-1}$, where $c$ is a constant yet to be determined. Write the equation in terms of the new sequence:

$$ b_n - c a_{n-1} = q (b_{n-1} - c a_{n-2} + q a_{n-2}).$$

Now clean up a little:

$$b_n = q b_{n-1} + \underset{(*)}{\underbrace{c a_{n-1} + q(q-c) a_{n-2}}}.$$

Now

$$ (*) = c (a_{n-1} + \frac{q(q-c)}{c} a_{n-2}).$$

If we select $c$ such that $\frac{q(q-c)}{c} = c$, then the equation takes the form

$$ b_n = (q+c) b_{n-1}.$$

Whose solution is then

$$b_n = b_1 (q+c)^n.$$

Let's solve the equation:

$$ q(q-c) = c^2 \Leftrightarrow c^2 + qc - q^2 =0 \Leftrightarrow c_{1,2} = q \frac{-1 \pm \sqrt{5}}{2},$$

and therefore

$$q+c = q \frac{1\pm \sqrt{5}}{2}.$$

This leads to the following two linearly independent solutions (provided $q\ne 0$):

$$b_n^1 = b_1^1 (\frac{1+\sqrt{5}}{2})^n,~b_n^2 = b_1^2 (\frac{1-\sqrt{5}}{2})^n).$$

I hope it is clear how to finish.