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.
 A: 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}
$$
A: 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}}
$$
