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?

  • 1
    $\begingroup$ The keyword you want is "linear recurrence relation." Everything is determined by the roots of what is called the characteristic polynomial. $\endgroup$ – Qiaochu Yuan Mar 10 at 22:29
  • $\begingroup$ Thanks for your reply. It is indeed straightforward to apply this technique to solve the first generalization. Is it legitimate to generalize this technique to the last generalization by considering an infinite characteristic polynomial? $\endgroup$ – Andy Mar 10 at 22:34

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

  • $\begingroup$ Thanks so much for your answer. Regarding the last generalization, is it possible to derive when $b_n=\sum_{i=0}^{n-1}b_i$, the generating function of $b_n$ is the same as the A011782? I know verifying the correctness is simple and I also know how to use this technique for any finite length recursion. $\endgroup$ – Andy Mar 12 at 20:28
  • $\begingroup$ The thing to notice is that the g.f. for A011782 is $(1-x)/(1-2x)$ = $1/(1-x-x^2-x^3-\dots)$. $\endgroup$ – Somos Mar 12 at 20:34

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


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


$$ (*) = 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.


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.


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.