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

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.

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

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