<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] $$(N-2n)^2 = (N-n)^2 + n^2 - 2n(N-n)$$
Hence,
\begin{align}
S_N(n) & = \dfrac{(N-2n)^2}{n!(N-n)!}\\
& = \dfrac{(N-n)^2 + n^2 - 2n(N-n)}{n!(N-n)!}\\
& = \dfrac{N-n}{n!(N-n-1)!} + \dfrac{n}{(n-1)! (N-n)!} - 2 \dfrac1{(n-1)!(N-n-1)!}\\
& = \dfrac1{n!(N-n-2)!} + \dfrac1{n!(N-n-1)!} + \dfrac1{(n-2)!(N-n)!} + \dfrac1{(n-1)!(N-n)!} - \dfrac2{(n-1)!(N-n-1)!}
\end{align}
Now note that from the binomial expansion of $2^{N-k-m}$, we have that
$$\sum_{n=\min(k,a)}^{\max(N-m,b)} \dfrac1{(n-k)!(N-n-m)!} = \dfrac{2^{N-k-m}}{(N-k-m)!}$$
Hence, $$\sum_{n=0}^{n=N} S_N(n) = \dfrac{2^{N-2}}{(N-2)!} + \dfrac{2^{N-1}}{(N-1)!} + \dfrac{2^{N-2}}{(N-2)!} + \dfrac{2^{N-1}}{(N-1)!} -2 \dfrac{2^{N-2}}{(N-2)!} = \dfrac{2^N}{(N-1)!}$$
</s>