5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.