Asymptotics of $f(n)=\frac{2}{n}\sum_{i=1}^{n-2}f(i) + 1$

Question

While solving a probability problem, I came across a recurrent relation which I can't solve: $f(0)=0, f(1)=1$, and

$$f(n)=\frac{2}{n}\sum_{i=1}^{n-2}f(i) + 1 \ \text{for } n\ge 2$$

I simplified it:

$$nf(n) = (n-1)f(n-1)+2f(n-2)+1,$$ and now I struggle to find anything about this sequence. I suspect, that $\lim\limits_{n\rightarrow +\infty}\dfrac{f(n)}{n}=a$ exists. I tried to rearrange the formula and got $$f(n)-f(n-1) = -\dfrac{1}{n}(f(n-1)-f(n-2)) + \dfrac{1}{n}f(n-2) + \dfrac{1}{n},$$

$$\dfrac{f(n)-f(n-1)}{n-(n-1)} = -\dfrac{1}{n}\dfrac{f(n-1)-f(n-2)}{(n-1)-(n-2)} + \dfrac{1}{n}f(n-2) + \dfrac{1}{n},$$

so I assume, by solving $y'=-\dfrac{y'}{x} + \dfrac{y}{x} + \dfrac{1}{x}$, that $f(n) = c(n+1) - 1$.

Would appreciate any insight into this problem. Also, by calculating it on computer, I found that this limit $\approx0.43$.

Answer 1

Let me change the notation a bit. Let $(a_n)_{n\geq 0}$ be the sequence defined recursively by

$$ a_0 = 0, \qquad a_1 = 1, \qquad a_{n} = \frac{2}{n}\sum_{k=1}^{n-2} a_k + 1 \quad \text{for $n \geq 2$}. $$

Let $f(z) = \sum_{n=0}^{\infty} a_n z^n$ be its generating function. Then a bit of computation shows that the above recurrence relation translates to the differential equation of the form

$$ f(0) = 0, \qquad f'(0) = 1, \qquad (1-z)f'(z) = \frac{1}{1-z} + 2z f(z). $$

This equation can be easily solved using the method of integrating factors, yielding the unique solution

$$ f(z) = \frac{1 - e^{-2z}}{2(z - 1)^2}. $$

Expanding the numerator as the Taylor series about $z = 1$ and reorganizing the resulting expression, we can write

$$ f(z) = \frac{1 - e^{-2}}{2(z - 1)^2} + \frac{e^{-2}}{z - 1} + g(z) $$

for some entire function $g(z) = \sum_{n=0}^{\infty} b_n z^n$. (Although it is possible to give an explicit expression for $b_n$, what is important here is that $b_n \to 0$ as $n\to\infty$.) So by comparing the Taylor expansion of both sides,

$$ a_n = \frac{1 - e^{-2}}{2} (n+1) - e^{-2} + b_n. \tag{*} $$

Since $b_n \to 0$ as $n \to \infty$, it follows that

$$ \lim_{n\to\infty} \frac{a_n}{n} = \frac{1 - e^{-2}}{2} \approx 0.4323323584. $$

Answer 2

The first relation and the fact that the two first values of $f$ are non-negative imply by a trivial induction that $f$ is non-negative at each rank. Now, let us prove that for all $n$, $f(n) \leqslant n$.

It is true at rank $0$ and $1$ and if $n \geqslant 2$ and $f(n - 1) \leqslant n - 1$ and $f(n - 2) \leqslant n - 2$, then, $$ nf(n) = (n - 1)f(n - 1) + 2f(n - 2) + 1 \leqslant (n - 1)^2 + 2(n - 2) + 1 = n^2 - 2. $$ We deduce that $f(n) \leqslant \frac{n^2 - 2}{n} \leqslant n$.

Now, write $g(n) = \frac{f(n)}{n} \in [0,1]$ when $n \geqslant 1$. The induction relation becomes, when $n \geqslant 3$, \begin{align*} n^2g(n) & = (n - 1)^2g(n - 1) + 2(n - 2)g(n - 2) + 1\\ & = n^2g(n - 1) - (2n - 1)g(n - 1) + (2n - 4)g(n - 2) + 1\\ & = n^2g(n - 1) - (2n - 1)(g(n - 1) - g(n - 2)) - 3g(n - 2) + 1. \end{align*} thus, if we set $h(n) = g(n) - g(n - 1)$ for all $n \geqslant 2$, we have, for all $n \geqslant 3$, $$ n^2h(n) + (2n - 1)h(n - 1) = -3g(n - 2) + 1. $$ In particular, since $g$ is bounded between $0$ and $1$, $h$ is bounded between $-1$ and $1$ and, $$ h(n) = -\frac{2n - 1}{n^2}h(n - 1) - \frac{3}{n^2}g(n - 2) + \frac{1}{n^2} = \textrm{O}\left(\frac{1}{n}\right) \rightarrow 0. $$ We deduce that, $$ h(n) = -\frac{2n - 1}{n^2}h(n - 1) - \frac{3}{n^2}g(n - 2) + \frac{1}{n^2} = \textrm{O}\left(\frac{1}{n^2}\right). $$ Therefore, $\sum |h(n)| < +\infty$ by the Riemann summation rule. We deduce that $\sum h(n)$ converges toward some real limit $l$ and $g(n) - g(1) = \sum_{k = 2}^n h(k) \rightarrow l$ so $g(n)$ converges toward $a = l + g(1)$. Since $0 \leqslant g \leqslant 1$, we deduce that $0 \leqslant a \leqslant 1$.

Answer 3

I would use generating functions. Let $g(x)=\sum_{n=1}^ \infty f(n)x^n$. Multiplying both sides of the recurrence relation $nf(n)-(n-1)f(n-1)=2f(n-2)+1$ by $x^{n-1}$ and adding we see that $$g’(x)=\frac{2x}{1-x}g(x)+\frac{1}{(1-x)^2}$$ From this follows that $$\frac{d}{dx}\left(e^{2x}(1-x)^2g(x)\right)=e^{2x}$$ Recalling that $g(0)=0$ we conclude that $$e^{2x}(1-x)^2g(x)=\frac{e^{2x}-1}{2}.$$ Equivalently $$\eqalign{g(x)&=\frac12\frac{1}{(1-x)^2}(1-e^{-2x})\cr &=\frac12\left(\sum_{n=0}^\infty (n+1)x^n\right)\left(\sum_{n=1}^\infty \frac{(-1)^{n-1}2^n}{n!}x^n\right)}$$ Thus $$ \eqalign{f(n)&=\frac12\sum_{k=1}^n(n+1-k)\frac{(-1)^{k-1}2^{k}}{k!}\cr &=\frac{n+1}{2} \sum_{k=1}^n\frac{(-1)^{k-1}2^{k}}{k!} -\sum_{k=1}^n(\frac{(-1)^{k-1}2^{k-1}}{(k-1)!}\cr &= \frac{n+1}{2}(1-e^{-2})-e^{-2}-\epsilon_n}$$ With $$\epsilon_n=\frac{n+1}{2} \sum_{k=n+1}^\infty\frac{(-1)^{k-1}2^{k}}{k!} -\sum_{k=n+1}^\infty(\frac{(-1)^{k-1}2^{k-1}}{(k-1)!}$$ Using the alternating series estimation of the remainder we see that $$\vert\epsilon_n\vert\le \frac{2^{n+1}}{n!}$$ We conclude that $$f(n)= \frac{n+1}{2}(1-e^{-2})-e^{-2}+O\left(\frac{2^n}{n!}\right).$$ This gives the required asymptotic expansion of $f(n)$.