For a solution of linear recurrence relation, $\lim_{n\to\infty}a_n^{1/n}$ is a zero of a related polynomial

48 Views Asked by At

On page 134 of J.H. van Lint's book A Course in Combinatorics, it says

from $a_n=5a_{n-1}-7a_{n-2}+4a_{n-3}$ $(n\ge5)$, we find that $\lim_{n\to\infty}a_n^{1/n}=\theta$, where $\theta$ is the zero with largest absolute value of the polynomial $x^3-5x^2+7x-4$.

I guess it is related to fixed point theory, but I'm not clear. May I have some help?

1

There are 1 best solutions below

0
On BEST ANSWER

You can re-write your recurrence like $a_{n}-5a_{n-1}+7a_{n-2}-4a_{n-3}=0$ this gives rise (through a transformation that you'd see in any intro combinatorics text) to the polynomial that have $x^3-5x^2+7x-4=0$. There are three solutions (maybe some are complex) to that equation, say $r_1, r_2, r_3$. Then, the closed form expression for you sequence will be something of the form (provided that the polynomial has no repeated roots):

$$a_{n} = C_1 r_{1}^{n} + C_2 r_{2}^{n} + C_3 r_{3}^{n}$$ where the $C_{i}$'s are constants chosen to satisfy your initial conditions. Suppose that $|r_1|>|r_2|>|r_3|$. Then

\begin{align*} \lim_{n\to\infty} a_{n}^{1/n} &= \lim_{n\to\infty}(C_1 r_{1}^{n} + C_2 r_{2}^{n} + C_3 r_{3}^{n})^{1/n} \\ &= \lim_{n\to\infty}r_{1}\left(C_1 + \frac{C_2 r_2^{n}}{r_1^{n}} + \frac{C_3 r_3^{n}}{r_1^{n}}\right)^{1/n} \end{align*}

Everything inside the parenthesis goes to $C_{1}$ in the limit, so taking the $1/n$th power converges to 1. Recall that $r_1$ is the root of that polynomial with largest modulus... essentially what this means is that the asymptotic growth rate of your sequence is $r_{1}^{n}$.

EDIT: Note that this requires that $C_1\neq 0$.