<s>[INST] simplify summation of factorial (random walk) I suspect that the expression
$$\sum_{n=0}^N \frac{(N-2n)^2}{n!(N-n)!}$$
simplifies to 
$$\frac{2^N}{(N-1)!}$$
But I cannot find the intermediate steps. Can someone give me a hint how I can deduce this result?
(The expression comes up when calculating the average final position after a random walk of $N$ steps.)
 [/INST] $$
\begin{align}
\sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!}
&=
\sum_{n=0}^N\frac{((N-n)-n)^2}{n!(N-n)!}
\\
&=
\sum_{n=0}^N\frac{(N-n)^2}{n!(N-n)!}+\sum_{n=0}^N\frac{n^2}{n!(N-n)!}-2\sum_{n=0}^N\frac{(N-n)n}{n!(N-n)!}
\\
&=
\sum_{n=0}^N\frac{n^2}{n!(N-n)!}+\sum_{n=0}^N\frac{n^2}{n!(N-n)!}-2\sum_{n=1}^{N-1}\frac1{(n-1)!(N-n-1)!}
\\
&=
2\sum_{n=0}^N\frac{n^2}{n!(N-n)!}-2\sum_{n=0}^{N-2}\frac1{n!(N-2-n)!}\;.
\end{align}
$$
Now consider
$$
\sum_{n=0}^m\binom mnq^n=(1+q)^m
$$
and thus
$$
\sum_{n=0}^m\frac{q^n}{n!(m-n)!}=\frac{(1+q)^m}{m!}\;.
$$
Applying $q\partial/\partial q$ twice yields
$$
\sum_{n=0}^m\frac{n^2q^n}{n!(m-n)!}=\frac{(1+q)^{m-1}}{(m-1)!}+q^2\frac{(1+q)^{m-2}}{(m-2)!}\;.
$$
Now setting $q=1$ yields
$$
\sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!}=2\left(\frac{2^{N-1}}{(N-1)!}+\frac{2^{N-2}}{(N-2)!}\right)-2\frac{2^{N-2}}{(N-2)!}=\frac{2^N}{(N-1)!}\;.
$$
</s>