<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] In the course of this post, you can see how to prove that $$\sum_{n=0}^Nn\binom{N}{n}=N2^{N-1}.\tag{1}$$ Two other nice facts we'll use are $$\sum_{n=0}^N\binom{N}{n}=2^N\tag{2}$$ and $$\binom{N+1}{n}=\binom{N}{n}+\binom{N}{n-1}.\tag{3}$$ From these facts, along with $\binom{N}{N+1}=0$, we see that $$\begin{align}\sum_{n=0}^{N+1}n^2\binom{N+1}{n} &= \sum_{n=0}^{N+1}n^2\binom{N}{n} + \sum_{n=0}^{N+1}n^2\binom{N}{n-1}\\ &= \sum_{n=0}^Nn^2\binom{N}{n} + \sum_{n=1}^{N+1}n^2\binom{N}{n-1}\\ &= \sum_{n=0}^Nn^2\binom{N}{n} + \sum_{n=0}^N(n+1)^2\binom{N}{n}\\ &= 2\sum_{n=0}^Nn^2\binom{N}{n} + 2\sum_{n=0}^Nn\binom{N}{n}+\sum_{n=0}^N\binom{N}{n}\\ &= 2\sum_{n=0}^Nn^2\binom{N}{n} + N2^N+2^N\\ &= (N+1)2^N+2\sum_{n=0}^Nn^2\binom{N}{n}.\end{align}$$ Note that $\sum_{n=0}^0n^2\binom{0}{n}=0=0(0+1)2^{0-2}$, and if $\sum_{n=0}^Nn^2\binom{N}{n}=N(N+1)2^{N-2}$, then by the above work, $$\begin{align}\sum_{n=0}^{N+1}n^2\binom{N+1}{n} &= (N+1)2^N+2\sum_{n=0}^Nn^2\binom{N}{n}\\ &= (N+1)2^N+N(N+1)2^{N-1}\\ &= (N+1)(N+2)2^{N-1},\end{align}$$ so inductively, we have the identity $$\sum_{n=0}^Nn^2\binom{N}{n}=N(N+1)2^{N-2}\tag{4}$$ for all $N\geq 0$.
Now, using $(1)$ $(2)$ and $(4)$, we can see that $$\begin{align}N!\sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!} &= \sum_{n=0}^N(N-2n)^2\binom{N}{n}\\ &= N^2\sum_{n=0}^N\binom{N}{n}-4N\sum_{n=0}^Nn\binom{N}{n}+4\sum_{n=0}^Nn^2\binom{N}{n}\\ &= N^22^N-N^22^{N+1}+N(N+1)2^N\\ &= N2^N,\end{align}$$ whence dividing by $N!$ yields $$\sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!} = \frac{2^N}{(N-1)!},$$ as desired.
</s>