Solving recurrence relation with embedded summation 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?
 A: 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.
A: $\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!}}}}
$$
