Prove that $\lim \frac{f^{(n)}(0)}{n!}=\frac{2}{k+1}$ Suppose $k$ is a fixed integer. $\{a_n\}_{n \in \mathbb{Z}}$ is a sequence determined by the following recursion: $\forall n <0, a_n=0. \\a_0=1$ $\forall n+k>0, a_{n+k}=\frac{1}{k} \sum_{i=0}^{k-1} a_{n+i}$.
Then the generating function $$f(z)=\frac{k}{k-(z+z^2+\dots+z^k)}$$
Prove that $\lim a_n =\lim \frac{f^{(n)}(0)}{n!}=\frac{2}{k+1}$
 A: Step 1. We first check that the limit exists.


*

*Method 1. Let $ \phi(z) = kz^k - (z^{k-1} + \cdots + 1)$ be the characteristic polynomial for the reucrrence relation. Following Kelenner's reasoning, we know $\phi$ can be written as
$$\phi(z) = k(z-1)\prod_{j=1}^{k-1}(z - \alpha_j),$$
where $\alpha_1, \cdots, \alpha_{k-1}$ are distinct complex numbers with modulus $<1$. So the general solution of $a_n$ is of the form $ a_n = c + \sum_{j=1}^{k-1} c_j \alpha_j^n $ for some constants $c, c_1, \cdots, c_{k-1} \in \mathbb{C}$, which converges to $c$ as $n\to\infty$.

*Method 2. Here is a method specific to the case when $a_n$ are real. Let us write
$$l_n = \inf_{k \geq n} a_k, \qquad 
 \alpha = \liminf_{n\to\infty} a_n, 
 \qquad u_n = \sup_{k\geq n} a_k,
 \qquad \beta = \limsup_{n\to\infty} a_n. $$
It is easy to check that $(a_n)$ is bounded. So $\alpha$ and $\beta$ are finite. Now it follows that, for any $i \in \{0, \cdots, k-1\}$,
$$ a_{n+i}
= k a_{n+k} - \sum_{\substack{0\leq j \leq k-1 \\ j \neq i}} a_{n+j}
\leq k a_{n+k} - (k-1) l_{n}. $$
By induction together with the recurrence relation, we find that $ a_{n+i} \leq k a_{n+k} - (k-1) l_n $ holds for all $i \geq 0$. Taking $\sup$ over $i$, we obtain  $u_n \leq k a_{n+k} - (k-1) l_n$. Taking $\liminf$,
$$ \beta \leq k\alpha - (k-1)\alpha = \alpha. $$
Since the reverse inequality $\alpha \leq \beta$ comes free, we obtain $\alpha = \beta$ and thus $(a_n)$ converges.

Step 2. Let us compute the limit. The following easy lemma is useful for our purpose:

Lemma. Assume that $(c_n)_{n\geq 0}$ is a sequence of complex numbers that converge to $\alpha \in \mathbb{C}$. Then
$$ \lim_{x \uparrow 1} \frac{\sum_{n=0}^{\infty} c_n x^n}{\sum_{n=0}^{\infty} x^n} = \alpha. $$

The proof is quite easy, and we postpone its proof to the end. Then by the lemma,
$$ \lim_{n\to\infty} a_n
= \lim_{x\uparrow 1} (1-x)f(x)
= \lim_{x\uparrow 1} \frac{k(1-x)}{k-\sum_{j=1}^{k} x^j}
\stackrel{(*)}{=} \frac{k}{\sum_{j=1}^{k} j}
= \frac{2}{k+1}. $$
At $\text{(*)}$ we utilized an easy version of the L'Hospital's rule. (Or you may appeal to the definition of the derivative plus differentiation rules.)

Proof of Lemma. Fix $N \geq 1$. Notice that for $x \in (0, 1)$ we have $\sum_{n=0}^{\infty} x^n = (1-x)^{-1}$ and hence
$$ \left| \frac{\sum_{n=0}^{\infty} c_n x^n}{\sum_{n=0}^{\infty} x^n} - \alpha \right|
\leq (1-x)\sum_{n=0}^{N-1}|c_n-\alpha|x^n + \sup_{n\geq N} |c_n - \alpha|. $$
Taking $\limsup$ as $x \uparrow 1$, we know that
$$ \limsup_{x\uparrow 1}\left| \frac{\sum_{n=0}^{\infty} c_n x^n}{\sum_{n=0}^{\infty} x^n} - \alpha \right| \leq \sup_{n\geq N} |c_n - \alpha|. $$
Since $N$ is arbitrary, we may let $N\to\infty$ to obtain the desired claim. ////
A: Denote the sequence 
$$a_{n+k} = \frac{a_n+a_{n+1}+\cdots+a_{n+k-1}}{k} $$
We are interested in finding $\lim a_n$. It is easy to see that, no matter what the initial values are, the limit always exist (because the roots of the characteristic equation is either $1$ or with absolute value $< 1$). Let $L$ be the limit. Denote $S_n = a_0 + a_1 +\cdots + a_n$.

Then from $$ka_{n+k} = a_n+a_{n+1}+\cdots+a_{n+k-1}$$
We see that $$k(S_n - a_0 - \cdots- a_{k-1} + \cdots + a_{n+k}) = kS_n - (k-1)a_0 - \cdots - a_{k-2} + (k-1)a_{n+1} + \cdots + a_{n+k-1} $$
Cancelling $S_n$ both sides gives
$$ka_{n+k} + (k-1) a_{n+k-1} + \cdots + a_{n+1} = a_0 + 2a_1 +\cdots + ka_{k-1} $$
The original initial condition amounts $a_{k-1} = 1$, and $a_0 = a_1 = \cdots = a_{k-2} = 0$. Letting $n\to \infty$ gives
$$\frac{k(k+1)}{2}L = k \implies L = \frac{2}{k+1}$$
A: I use the formula you have shown. First, note that $\alpha_1=1$ is a root of the polynomial $z^k+\cdots+z-k$, and this is a simple root. Let $\alpha$ be a root (in $\mathbb{C}$) different from $1$. If $|\alpha|<1$, we get immediately from $|k|=|\alpha^k+\cdots+\alpha |\leq |\alpha|^k+\cdots+|\alpha|<k$ a contradiction. If $|\alpha|=1$, we get that, taking the conjugate $\alpha^{-k}+\cdots+\alpha^{-1}=k$, and multipling by $\alpha^{k+1}$, one show that $\alpha^{k+1}=1$. As $\alpha$ is not $1$, we get $1+\alpha+\cdots+\alpha^k=0$, ie $k+1=0$, a contradiction. Hence we have as root $\alpha_1=1$, and the other roots $\alpha_j$, $j=2,\cdots k$, are such that $|\alpha_j|>1$. Note also that the roots are all simple. To see why, show that $z^k+\cdots+z-k=(z-1)(z^{k-1}+2z^{k-2}+\cdots+k)$ and if we have a multiple root, then we must have in addition that $kz^{k-1}+\cdots+1=0$, and adding to $z^{k-1}+2z^{k-2}+\cdots+k=0$, we get $(k+1)(z^{k-1}+\cdots+1)=0$, in contradiction with the fact that the roots different from $1$ have absolute value $>1$.
Now write your $f(z)$ using simple fractions:
$$f(z)=\frac{A_1}{z-1}+\frac{A_2}{z-\alpha_2}+\cdots+\frac{A_k}{z-\alpha_k}$$
 We find $A_1$ using the fact that $A_1$ is the limit of $ (z-1)f(z)$ for $z\to 1$; we have that $\displaystyle \frac{z^k+\cdots+z-k}{z-1}$ has for limit the value of the derivative of $z^k+\cdots+z-k$ at $z=1$, and finally that $A_1=-\frac{2}{k+1}$. Now we write for $j\geq 2$
 $$\frac{A_j}{z-\alpha_j}=-\frac{A_j}{\alpha_j}\frac{1}{1-z/\alpha_j}=-\sum_{n\geq 0}\frac{A_j}{\alpha_j^{n+1}}z^n$$
and we get that
 $$a_n=\frac{2}{k+1}-\sum_{j=2}^k \frac{A_j}{\alpha_j^{n+1}}$$
 and it is easy to finish. 
