Solving recurrence relation with embedded summation

Question

I have the following recurrence:

$$F(0) = 0$$ $$F(1) = 1$$ $$nF(n) = n + 2 \sum_{i=1}^{n-2} F(i)$$

I'm new to generating functions, and I'm not sure how I would apply them here to try and get a closed form. I've written some programs that seem to imply empirically that:

$$\lim_{n\to\infty} \frac{F(n)}n = \frac{1 - {e}^{-2}}2$$

Is there some way to get the closed form for $F(n)$, or if not, just to prove the above limit?

Answer 1

After playing with the sequence for a bit, I realized that it was natural to write $F(n)$ as a fraction with denominator $n!$. The resulting numerators of $F(n)$ for $n=0,\ldots,5$ are $0,1,2,10,48,296$. OEIS returns exactly one candidate for this sequence, OEIS A037256. It is not immediately evident from the OEIS entry that this actually is the the sequence $\langle n!F(n):n\in\Bbb N\rangle$, but one of the references is to A seating arrangement problem [PDF] by Philippe Flajolet, which deals with the following problem (in a different formulation).

You have $n$ lights numbered $1$ through $n$; they start out off. As long as there is at least one light that is not adjacent to a light that is on, you choose one such light at random (uniform distribution) and turn it on. Let $E(n)$ be the expected number of light that are on when no more can be turned on. What is $E(n)$?

Say the first light turned on is number $k$. Then lights $k-1$ and $k+1$ are no longer available to be turned on, and we can now work separately in the block of lights numbered $1$ through $k-2$ and the block numbered $k+2$ through $n$. The expected number of lights turned on will then be $1+E(k-2)+E(n-k-1)$, and since each of the $n$ choices of $k$ is equally likely, we must have

$$\begin{align*} E(n)&=\frac1n\sum_{k=1}^n\big(1+E(k-2)+E(n-k-1)\big)\\ &=1+\frac1n\left(\sum_{k=1}^nE(k-2)+\sum_{k=1}^nE(n-1-k)\right)\\ &=1+\frac1n\left(\sum_{k=1}^{n-2}E(k)+\sum_{k=1}^{n-2}E(k)\right)\\ &=1+\frac2n\sum_{k=1}^{n-2}E(k)\;. \end{align*}$$

Multiplying through by $n$, we find that

$$nE(n)=n+2\sum_{k=1}^{n-2}E(k)\;,$$

and clearly $E(0)=0$ and $E(1)=1$, so in fact $E(n)=F(n)$.

We can now use the information in the OEIS entry:

$$F(n)=\sum_{k=0}^{n-1}\frac{(n-k)(-2)^k}{(k+1)!}\;,$$

and if $a_n=n!F(n)$, the numbers $a_n$ satisfy the recurrence

$$a_n=2(n-1)a_{n-1}-(n-4)(n-1)a_{n-2}-2(n-2)(n-1)a_{n-3}$$

and have the exponential generating function

$$g(x)=\frac{1-e^{-2x}}{2(1-x)^2}=\sum_{n\ge 0}a_n\frac{x^n}{n!}=\sum_{n\ge 0}F(n)x^n\;,$$

which is therefore the ordinary generating function for your sequence.

Finally, $a_n\sim\frac12nn!(1-e^{-2})$, so

$$F(n)\sim\frac{n(1-e^{-2})}2\;,$$

as you conjectured.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{n\,\mrm{F}\pars{n} = n + 2 \sum_{i = 1}^{n - 2}\mrm{F}\pars{i}\,,\qquad \mrm{F}\pars{0} = 0\,,\quad\mrm{F}\pars{1} = 1}$.

$$\bbox[25px,#ffe,border:1px dotted navy]{\ds{% \begin{array}{c} \mbox{We'll find}\ \mrm{F}\pars{n}\ \mbox{by means of the}\ Generating\ Function\ \ds{\mc{F}\pars{z}}: \\[2mm] \ds{\mc{F}\pars{z} \equiv \sum_{n = 0}^{\infty}\mrm{F}\pars{n}z^{n} \quad\iff\quad \mrm{F}\pars{n} = \bracks{z^{n}}\mc{F}\pars{z}} \end{array}}} $$

---

\begin{align} \sum_{n = 0}^{\infty}n\,\mrm{F}\pars{n}z^{n} & = \sum_{n = 0}^{\infty}n\, z^{n} + 2\sum_{n = 0}^{\infty}z^{n} \sum_{i = 0}^{\infty}\mrm{F}\pars{i}\bracks{i \leq n - 2} \\[5mm] z\,\partiald{}{z}\sum_{n = 0}^{\infty}\mrm{F}\pars{n}z^{n} & = {z \over \pars{1 - z}^{2}} + 2\sum_{i = 0}^{\infty}\mrm{F}\pars{i} \sum_{n = i + 2}^{\infty}z^{n} = {z \over \pars{1 - z}^{2}} + 2\sum_{i = 0}^{\infty}\mrm{F}\pars{i} \sum_{n =0}^{\infty}z^{n + i + 2} \\[5mm] & = {z \over \pars{1 - z}^{2}} + 2\,{z^{2} \over 1 - z} \sum_{i = 0}^{\infty}\mrm{F}\pars{i}z^{i} \end{align}

---

The Generating Function $\ds{\color{#f00}{\mc{F}\pars{z}} \equiv \color{#f00}{\sum_{n = 0}^{\infty}\mrm{F}\pars{n}z^{n}}}$ satisfies $\ds{\pars{~\mbox{note that}\ \color{#f00}{\,\mrm{F}\pars{n} = \bracks{z^{n}}\mc{F}\pars{z}}~}}$ \begin{align} \partiald{\mc{F}\pars{z}}{z} - {2z \over 1 - z}\,\mrm{F}\pars{z} = {1 \over \pars{1 - z}^{2}}\,,\qquad \mc{F}\pars{0} = \mrm{F}\pars{0} = 0 \end{align} This is equivalent to: \begin{align} \partiald{}{z}\bracks{\expo{2z}\pars{1 - z}^{2}\,\mc{F}\pars{z}} = \expo{2z} &\implies \expo{2z}\pars{1 - z}^{2}\,\mc{F}\pars{z} = {1 \over 2}\,\expo{2z} - {1 \over 2} \\[5mm] &\implies \mc{F}\pars{z} = {1 \over 2}\,{1 \over \pars{1 - z}^{2}} - {1 \over 2}\, {\expo{-2z} \over \pars{1 - z}^{2}} \end{align} and \begin{align} \mc{F}\pars{z} & = {1 \over 2}\sum_{n = 0}^{\infty}\pars{n + 1}z^{n} - {1 \over 2}\sum_{j = 0}^{\infty}{\pars{-2z}^{\, j} \over j!} \sum_{k = 0}^{\infty}\pars{k + 1}z^{k} \\[5mm] & = {1 \over 2}\sum_{n = 0}^{\infty}\pars{n + 1}z^{n} - {1 \over 2}\sum_{j = 0}^{\infty}\pars{-1}^{\, j}{2^{\, j} \over j!} \sum_{k = 0}^{\infty}\pars{k + 1}\sum_{n = 0}^{\infty}z^{n}\,\delta_{n,k + j} \\[5mm] & = {1 \over 2}\sum_{n = 0}^{\infty}\pars{n + 1}z^{n} - {1 \over 2}\sum_{n = 0}^{\infty}\bracks{% \sum_{j = 0}^{n}\pars{-1}^{\, j}{2^{\, j} \over j!}\pars{n - j + 1}}z^{n} \end{align}

---

$$\bbox[15px,#ffe,border:1px dotted navy]{\ds{% \mrm{F}\pars{n} = {1 \over 2}\bracks{% n + 1 - \sum_{j = 0}^{n}\pars{-1}^{\, j}\pars{n - j + 1}\,{2^{\,j} \over j!}}}} $$