Find limit of $(a_n)$ if $a_n=\frac{1}{k}\sum\limits_{i=1}^{k}a_{n-i}$, $a_0=1$ and $a_{-n}=0$ for $n>0$

Question

We have a sequence $a_n$ which solves the recurrence relation

$$a_n=\frac{1}{k}\sum\limits_{i=1}^{k}a_{n-i}$$ for any $n>0$ with a given $k$. Let the initial values be $a_0=1$ and $a_{-n}=0$ for any $n>0$.

I wrote a program and found that the sequence should have a limit $\frac{2}{k+1}$, but I can't figure out how to prove it.

Answer 1

Your equation can be rewritten in the form of a renewal equation: $$ a_n = b_n +(a*p)_n $$ where, for every $n\ge0$, $$p_n =\frac{1}{k}1_{1\le n\le k}\qquad b_n=1_{n=0}$$ and $$ (a*p)_n :=\sum_{j=0}^n a_{n-j}p_j $$ Here, $\{b_j\}$ is added since $a_n =\frac{1}{k}\sum\limits_{j=1}^k a_{n-j}$ does not hold for $n=0$.

Now, it is a result of the (discrete version of) Blackwell's renewal theorem that $$ \lim_{n\to\infty} a_n =\frac{\sum\limits_{n=0}^\infty b_n}{\sum\limits_{n=0}^\infty np_n}=\frac{1}{\frac{1}{k}\frac{k(k+1)}{2}}=\frac{2}{k+1} $$

Answer 2

Could be of help to associate to the cute answer already given, the expression of the generating function (z-Transform).

We have $$ a_{\,n} = {1 \over k}\sum\limits_{1\, \le \,i\, \le \,k} {a_{\,n\, - \,i} } + \left[ {n = 0} \right] = {1 \over k}\sum\limits_i {\left[ {1\, \le \,i\, \le \,k} \right]a_{\,\,n\, - \,i} } + \left[ {n = 0} \right] $$ where $[P]$ denotes the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

The generating function will then be $$ \eqalign{ & A(z) = \sum\limits_{0\, \le \,n} {a_{\,n} \,z^{\,n} } = {1 \over k}\sum\limits_{0\, \le \,n} {\sum\limits_i {\left( {\left[ {1\, \le \,i\, \le \,k} \right]z^{\,i} } \right)\left( {a_{\,\,n\, - \,i} \,z^{\,n - i} } \right)} } + 1 = \cr & = {1 \over k}\left( {\sum\limits_{0\, \le \,n} {\left[ {1\, \le \,n\, \le \,k} \right]z^{\,n} } } \right) \sum\limits_{0\, \le \,n} {\left( {a_{\,\,n\,} \,z^{\,n} } \right)} + 1 = \cr & = {1 \over k}\left( {z\sum\limits_{1\, \le \,n\, \le \,k} {z^{\,n - 1} } } \right)\sum\limits_{0\, \le \,n} {\left( {a_{\,\,n\,} \,z^{\,n} } \right)} + 1 = \cr & = {1 \over k}\left( {z{{1 - z^{\,k} } \over {1 - z}}} \right)A(z) + 1 \cr} $$ that is $$ A(z) = {1 \over {1 - {z \over k}\left( {{{1 - z^{\,k} } \over {1 - z}}} \right)}} = {{1 - z} \over {z^{\,k} - \left( {k + 1} \right)z + k}} $$