Generating function of $a_n = \sum_{k = 0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k}\frac{(2k)!}{k!2^k}$ is $e^{x+x^2/2}$? I need to prove that the generating function of $a_n = \sum\limits_{k = 0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k}\dfrac{(2k)!}{k!2^k}$ is $e^{x+x^2/2}$.
I tried it like this. I know that $e^x=\sum_{i=0}^{\infty}\dfrac{x^i}{i!}$
So $e^{x+x^2/2}=\sum_{i=0}^{\infty}\dfrac{(x(1+\dfrac{x}{2}))^i}{i!}=\sum_{i=0}^{\infty}\dfrac{x^i\sum_{j=0}^i{i\choose j}\left(\dfrac{x}{2}\right)^j}{i!}$
Let's get the coefficient next to  $x^k$.
$\dfrac{x^i{i\choose j}\left(\dfrac{x}{2}\right)^j}{i!}$ will have an $x$ in $k$'th power, when $i+j=k$ and $j\leq i \leftrightarrow j\leq k-j \leftrightarrow 2j\leq k$
Let's put $i=k-j$ , then
$\dfrac{x^{k}{k-j\choose j}}{(k-j)! 2^j}$
An I'm stuck...
 A: Think of $e^{x+x^2/2}$ as $e^x\cdot e^{x^2/2}$: the series is
$$\left(\sum_{n\ge 0}\frac1{n!}\left(\frac{x^2}2\right)^n\right)\left(\sum_{n\ge 0}\frac{x^n}{n!}\right)=\left(\sum_{n\ge 0}\frac{x^{2n}}{2^nn!}\right)\left(\sum_{n\ge 0}\frac{x^n}{n!}\right)\;,$$
in which the $x^n$ term is
$$\begin{align*}
\sum_{k=0}^{\lfloor n/2\rfloor}\left(\frac1{2^kk!}\cdot\frac1{(n-2k)!}\right)x^n&=\sum_{k=0}^{\lfloor n/2\rfloor}\frac{n!}{2^kk!(n-2k)!}\left(\frac{x^n}{n!}\right)\\\\
&=\sum_{k=0}^{\lfloor n/2\rfloor}\left(\frac{n!}{(2k)!(n-2k)!}\cdot\frac{(2k)!}{2^kk!}\cdot\frac{x^n}{n!}\right)\\\\
&=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}\frac{(2k)!}{2^kk!}\left(\frac{x^n}{n!}\right)\\\\
&=a_n\left(\frac{x^n}{n!}\right)\;,
\end{align*}$$
so $e^{x+x^2/2}$ is the exponential generating function of $\langle a_n:n\in\Bbb N\rangle$.
A: Here is a combinatorial proof. Note that the species of involutions (permutations $\sigma$ such that $\sigma^2 = \mathrm{Id}$) is given by 
$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z})+\mathfrak{C}_{=2}(\mathcal{Z})).$$
Therefore it has EGF $$f(z) = \exp(z+z^2/2).$$
Now to prove that $f(z)$ is the EGF of
$$\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} \frac{(2k)!}{k! 2^k}$$
we just need to show that the above sum counts involutions.
This is straightforward to see. Choose $2k$ elements from $n$ that will form two-cycles and let the rest be fixed points. Line up your $2k$ elements from left to right getting $(2k)!$ permutations and form two-cycles from adjacent elements. Then we need to divide by $2^k$ because the cycle $(a,b)$ is the same as $(b,a).$ Moreover every permutation of two-cycles shows up $k!$ times on the line. This concludes the argument.
