# Limit of a Recursive Sequence

### Leonard Giugiuc, Dan Sitaru 23 December, 2015

The following problem is due to Arkady Alt:

Let $k\ge 2$ be a fixed integer; $x_0,x_1,\ldots,x_{k-1}$ complex numbers and

$\displaystyle x_{n+1}=\frac{1}{k}\sum_{s=0}^{k-1}x_{n-s},$ for $n\ge k-1.$

Find $\displaystyle\lim_{n\rightarrow\infty}x_n.$

### Solution

First, we introduce two lemmas:

### Lemma 1

Let $\{a_n\}$ be a sequence of complex numbers such that $a_n\ne 0,\;$ $n\ge 0.$ If $\displaystyle\lim_{n\rightarrow\infty}\left|\frac{a_{n+1}}{a_n}\right|\lt 1,\;$ then $\displaystyle\lim_{n\rightarrow\infty}a_n=0.$

For a proof, observe that Lemma holds for a real-valued sequence, and so does for $\{|a_n|\}.$ It follows that $\displaystyle\lim_{n\rightarrow\infty}|a_n|=0\;$ and, therefore, also $\displaystyle\lim_{n\rightarrow\infty}a_n=0.$

### Lemma 2

Let $z$ be a complex number, with $|z|\lt 1,\;$ and $m\ge 1\;$ an integer. Then $\displaystyle\lim_{n\rightarrow\infty}n^mz^n=0.$

For a proof, assume $z\ne 0,$ for, otherwise, there is nothing to prove. Let $a_n=n^mz^n.$ We have

$\displaystyle\lim_{n\rightarrow\infty}\left|\frac{a_{n+1}}{a_n}\right|=\lim_{n\rightarrow\infty}\left[\left(\frac{n+1}{n}\right)^m\cdot|z|\right]=|z|\lt 1.$

Hence, by Lemma 1, $\displaystyle\lim_{n\rightarrow\infty}a_n=0\;$ i.e., $\displaystyle\lim_{n\rightarrow\infty}n^mz^n=0,$ as required.

To continue, by the definition, sequence $\{a_n\}$ obeys a linear recurrence of order $k,\;$ with the characteristic polynomial

$\displaystyle P(x)=kx^k-\sum_{s=0}^{k-1}x^s=(x-1)\sum_{s=0}^{k-1}(s+1)x^s.$

If $\displaystyle f(x)=\sum_{s=0}^{k-1}(s+1)x^s,\;$ then $f(1)\ne 0\;$ so that the multiplicity of $1\;$ as a root of $P(x)\;$ is $1.\;$ Also, $f(-1)\ne 0.$

Let $z$ be a root of $P,$ other than $1.\;$ We'll show that $|z|\lt 1.\;$ Indeed, $P(z)=0\;$ implies $\displaystyle kz^k=\sum_{s=0}^{k-1}z^s$ and, subsequently, $\displaystyle |kz^k|=\left|\sum_{s=0}^{k-1}z^s\right|.\;$ Let $|z|=r.\;$ Assume, for a contradiction, that $r\ge 1.\;$ Combined with the above, this would imply $\displaystyle kr^k\ge\sum_{s=0}^{k-1}r^s\;$ and, further, $\displaystyle kr^k=\sum_{s=0}^{k-1}r^s\;$ from which $r=1.\;$

Now, we have assumed that $z\ne 1$ and observed that, as a root of $P,\;$ $z\ne -1.\;$ Hence $z$ is not real. But the equality $\displaystyle |\sum_{s=0}^{k-1}z^s|=\sum_{s=0}^{k-1}r^s\;$ only holds if $z$ is real which is a desired contradiction. Thus, $|z|\lt 1.$

Let $z_1,z_2,\ldots,z_m$ be the roots of $P$ (other than $1)$ with the multiplicities $s_1,s_2,\ldots,s_m.\;$ Then the theory of linear recurrences informs us that there exists a complex number $\alpha\;$ and polynomials $P_t,\;$ $t=1,2,\ldots,m,\;$ such that $\deg P_t=s_t-1\;$ and $\displaystyle x_n=\alpha+\sum_{t=1}^{m}P_{t}(n)\cdot z_t^n,\;$ for all $n\ge 0.$

By Lemma 2, $\displaystyle \lim_{n\rightarrow\infty}\left[\sum_{t=1}^{m}P_{t}(n)\cdot z_t^n\right]=0,\;$ so that $\displaystyle\lim_{n\rightarrow\infty}x_n=\alpha.$

On the other hand, we can easily verify that $\displaystyle\sum_{s=0}^{k-1}(k-s)x_{n-s}=\sum_{s=0}^{k-1}(s+1)x_{s}.\;$ As we pass to the limit, we get $\displaystyle\frac{k(k+1)}{2}\cdot\alpha=\sum_{s=0}^{k-1}(s+1)x_{s},\;$ such that $\displaystyle\alpha=\frac{2}{k(k+1)}\sum_{s=0}^{k-1}(s+1)x_{s}.$