solving a linear recurrence relation simple moving average Here's a recurrence relation, $k$ is fixed:
$$\frac{1}{k}\sum_{n=i}^{k+i-1} a_n = a_{k+i}$$ for all $i\in \mathbb{N}$, and for $a_i$ with $1\leq i \leq k$ we have fixed non-negative real number intial conditions (i.e. $a_i \geq 0$).  Find necessary and sufficient conditions for convergence of $\{a_n\}$.
I can show this is a bounded sequence and that the infimum and supremum of the sequence approach each other, however I cannot show that they are the same thing... thoughts? The reason it is difficult for me is because the method of using characteristic polynomials is that their degree is different for each $k$.
 A: Use generating functions. Define $A(z) = \sum_{i \ge 0} a_i z^i$. Write the recurrence as:
$\begin{align}
a_{n + k} = \frac{1}{k} \sum_{0 \le n \le k - 1} a_{i + n}
\end{align}$
Multiply by $z^i$, sum over $i \ge 0$, and recognize the sums:
$\begin{align}
\sum_{i \ge 0} a_{i + r} z^i
  = \frac{A(z) - a_0 - a_1 z - \dotsb - a_{r - 1} z^{r - 1}}{z^r}
\end{align}$
multiply through by $z^k$, solve for $A(z)$ to get:
$\begin{align}
A(z) \left(1 - \frac{1}{k} \sum_{0 \le n \le k - 1} z^{k - n} \right)
  &= P(z) \\
A(z) \left( 1 - \frac{1}{k} \cdot \frac{z (1 - z^k)}{1 - z} \right)
  &= P(z)
\end{align}$
Here $P(z)$ is a polynomial of degree at most $k - 1$ that depends on the initial values. We are interested in the zero of smallest absolute value of the polynomial that ends up as denominator:
$\begin{align}
z^k + z^{k - 1} + \dotsb + z - k
\end{align}$
By Descartes' rule of signs this has one real positive zero, which is seen to be $1$. Long division by $z - 1$ yields:
$\begin{align}
p(z) = \sum_{1 \le s \le k} s z^{k - s}
\end{align}$
To get a lower bound for the absolute values of the zeros of this polynomial is to get an upper bound for the zeros of:
$\begin{align}
u^{k - 1} p(u^{-1})
  = \sum_{0 \le s \le k - 1} (s + 1) u^s 
\end{align}$
The Fujiwara bound tells us that all zeros of the last one have absolute values less than:
$\begin{align}
2 \max \left\{
         \frac{k}{k + 1},
            \left(\frac{k - 1}{k}\right)^{1/2},
            \dotsc,
            \left(\frac{1}{2 k}\right)^{1/(k - 1)}
       \right\}
   = \frac{2 k}{k + 1}
\end{align}$
so all zeros of $p(z)$ have absolute value larger than $1$ if $k > 1$. Thus the solutions converge. And the only value to which they can converge is:
$\begin{align}
\frac{1}{k} \sum_{0 \le n \le k - 1} a_n
\end{align}$
