Limit of sequence in which each term is defined by the average of preceding two terms

There are answers in the link above which show methods on finding this limit and are relatively easy to generalise, when specified a $k$. However, when attempting to generalise for any $k$, it gets extremely messy with sigma notation after a few steps of incorporating, let's say, Arnaldo's method. Is there a more elegant way to prove:

For a given $u_1, u_2, ... u_k$ and that the nth term of the sequence $u_n$ is the average of its previous $k$ terms,

$$ u_n = \frac{1}{k} \sum_{i=1}^{k}{u_{n-i}} $$

the limit of $u_n$ as $n \rightarrow \infty$ is

$$ \frac{\sum_{i=1}^{k} {iu_i}}{\sum_{i=1}^{k}{i}} = \frac{2}{k(k+1)} \sum_{i=1}^{k} {iu_i} $$


This is a linear recursion relationship. The methods for calculating formulas for the $n$ term are well known. In particular, we can form a vector for $k$ adjacent elements of the sequence: $$U_i = \begin{bmatrix}u_{i+k}\\u_{i+k-1}\\\vdots\\u_i\end{bmatrix}$$

Then we find that $$U_{i+1} = AU_i$$ where $$A = \begin{bmatrix}\frac 1k & \frac 1k & \frac 1k & \dots & \frac 1k \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\\vdots & \vdots & \vdots & \ddots & \vdots\\ 0&0&0&\dots & 1\end{bmatrix}$$

And more generally $U_{n+1} = A^nU_1$. If $A$ can be diagonalized, then there exist matrices $Q, Q^{-1}, D$ with $D$ having only diagonal entries (the eigenvalues of $A$) such that $A = QDQ^{-1}$. And therefore $$U_{n+1} = QD^nQ^{-1}U_0$$ If $$D = \begin{bmatrix}a_k & 0 & \dots & 0 \\ 0 & a_{k-1} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots\\ 0&0&\dots & a_1\end{bmatrix}$$ which I'll abbreviate to $D = [[a_k \dots a_1 ]]$, then $D^n = [[a_k^n \dots a_1^n ]]$. So $$U_{n+1} = Q[[a_k^n \dots a_1^n ]]Q^{-1}U_1$$

Now the expression $Q[[a_k^n \dots a_1^n ]]Q^{-1}U_1$ depends linearly on each of the $a_k^n$. In particular, there exist constants $B_i$ such that $$u_n = B_1a_1^n + B_2a_2^n + \dots + B_ka_k^n$$ The characteristic polynomial of $A$ is $$x^k - \frac 1k\left(x^{k-1} + ... + x + 1\right)$$ so the eigenvalues $a_i$ are its roots. It is easily checked that the first root is $a_1 = 1$. And a look at the derivative shows that $1$ is not a multiple root. I'll leave determining the other roots to you. If they are distinct, then $A$ is diagonalizable.

Once the eigenvalues are determined, it is not necessary to figure out $Q$. Instead you can solve the system of equations formed by $$u_n = B_1a_1^n + B_2a_2^n + \dots + B_ka_k^n$$ when $n =1 \dots k$ for the constants $B_i$.

Now taking the limit $$\lim u_n = B_1\lim a_1^n + B_2\lim a_2^n + \dots + B_k\lim a_k^n$$

Provided the limits on the right-hand side converge. Since the eigenvalues may be complex, we have $4$ cases:

  • $|a_i| < 1$, in which case $\lim_n a_i^n = 0$.
  • $a_i = 1$, in which case $\lim_n a_i^n = 1$.
  • $|a_i| = 1$ and $a_i \ne 1$, in which case $\lim_n a_i^n$ does not converge.
  • $|a_i| > 1$, in which case $\lim_n a_i^n = \infty$.

For your supposition to be correct, the limit must converge to a finite value, which means you will need to show that for $i> 1, |a_i| < 1$. In this case, $$\lim u_n = B_1$$so you will also need to show that $B_1$ has the desired form.


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.