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.)
 A: You're right. Multiplying both sides by $N!$, one gets:
$$\sum_{n=0}^{N} (N-2n)^2 \binom{N}{n} = N2^{N}$$
3 Lemmas, based on $\binom{n}{k}=\frac{n}{k} \binom{n-1}{k-1}$ (note that in each lemma I apply the previous lemmas):


*

*$\sum_{n=0}^{N}\binom{N}{n} = 2^{N}$

*$\sum_{n=0}^{N} n\binom{N}{n} = N\sum_{n=1}^{N} \binom{N-1}{n-1} = N2^{N-1}$

*$\sum_{n=0}^{N} n^2\binom{N}{n} = N\sum_{n=1}^{N} n\binom{N-1}{n-1} = N(\sum_{n=1}^{N} (n-1)\binom{N-1}{n-1} + \sum_{n=1}^{N} \binom{N-1}{n-1})=N((N-1)2^{N-2} + 2^{N-1})$


So now it is just a matter of expanding the original sum:
$$\sum_{n=0}^{N} (N-2n)^2 \binom{N}{n} = N^2 \sum_{n=0}^{N}\binom{N}{n} - 4N \sum_{n=0}^{N} n \binom{N}{n} +4 \sum_{n=0}^{N} n^2\binom{N}{n} = N^2 2^N -4N^{2}2^{N-1}+4N((N-1)2^{N-2}+2^{N-1})=N2^{N}$$
EDIT: As I see this kind of question quiet often, I'll present a guide on how to simplify $\sum_{k=0}^{n} P(n,k)\binom{n}{k}$ for any polynomial $P$, in your case - $(n-2k)^2$.
Step 1: Reduce to calculating $\sum_{k=0}^{n} k^i \binom{n}{k}$ by calculating the original sum monom-wise.
Step 2: Note that $$\sum_{k=0}^{n} \binom{k}{i} \binom{n}{k} = \binom{n}{i} 2^{n-i}$$
This identity generalizes my lemma. It can be proved by many ways:


*

*By induction on $i$ (as in the lemmas, use $\binom{k}{i} \binom{n}{k} = \binom{k-1}{i-1} \binom{n-1}{k-1}\frac{n}{i}$)

*By differentiating the identity $\sum_{k=0}^{n} \binom{n}{k} x^k = (1+x)^n$ $i$ times, dividing by $i!$ and plugging $x=1$. 

*There's also a combinatorial proof (LHS counts ways to pick a special subset of $i$ people out of $n$, and then choosing a set containing them, of size $k$, as $k$ runs from $0$ to $n$).

*A short direct proof: $\binom{k}{i} \binom{n}{k} = \binom{n}{i}\binom{n-i}{n-k}$.


Step 3: Write $k^i$ as a combination of $\binom{k}{j}$ for $j\le i$, and apply step 2. Don't worry, there's a shortcut as always: $$k^i = \sum_{j=0}^{i} c_{i,j} \binom{k}{j}$$
$$c_{i,j} = \# \{ \text{surjective functions from i-set to j-set} \}$$
This again has both algebraic and combinatorial proofs. 


*

*The algebraic goes along the lines of calculating the $j$'th discrete derivative of $f(k)=k^i$ at $0$, obtaining $c_{i,j}$ and deciphering what it counts (it equals the sum $\sum_{t=0}^{j} t^i(-1)^{t-j} \binom{j}{t}$ - inclusion-exclusion anyone?). 

*But the combinatorial one is cooler - note that $k^i$ counts the number of functions from a $i$-set to a $k$-set, and then understand the RHS.


Conclusion - you'll always get the simplification $2^n Q(n)$, where $Q$ is a polynomial depending linearly on $P(n,k)$.
I just love the interplay between the algebraic and combinatorial solutions...
A: $$(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)!}$$
A: Note that $\sum_{n=0}^{N}\frac{x^{2n}}{n!(N-n)!}=\frac{(1+x^2)^N}{N!}$. Thus:
$$\sum_{n=0}^{N}\frac{x^{2n-N}}{n!(N-n)!}=\frac{x^{-N}(1+x^2)^N}{N!}$$
Now diffrentiate with repect to $x$ to get:
$$\sum_{n=0}^{N}\frac{(2n-N)x^{2n-N-1}}{n!(N-n)!}=\frac{d}{dx}[\frac{x^{-N}(1+x^2)^N}{N!}]$$
Multiply by $x$ to get:
$$\sum_{n=0}^{N}\frac{(2n-N)x^{2n-N}}{n!(N-n)!}=x\frac{d}{dx}[\frac{x^{-N}(1+x^2)^N}{N!}]$$
Diffrentiate with respect to $x$ to get:
$$\sum_{n=0}^{N}\frac{(2n-N)^2x^{2n-N-1}}{n!(N-n)!}=\frac{d}{dx}[x\frac{d}{dx}[\frac{x^{-N}(1+x^2)^N}{N!}]]$$
Now let $x=1$ to get your sum on the LHS.
A: $$
\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)!}\;.
$$
A: 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.
A: Let $S_N$ be that sum.  Then the generating function for $S_N$ is
$$
\sum_{N=0}^{\infty} S_Nx^N =
\sum_{N=0}^{\infty} \sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!}x^N = \sum_{n=0}^{\infty} \sum_{N=0}^{\infty}\frac{(N-n)^2}{n!N!}x^{N+n} = \\
\sum_{n=0}^{\infty} \sum_{N=0}^{\infty}\frac{n+N+2}{n!N!}x^{N+1+n} -2\sum_{n=0}^{\infty}\sum_{N=0}^{\infty} \frac{1}{n!N!}x^{N+n+2} =\\
\frac{\partial}{\partial x}\left(x^2 e^{2x}\right) - 2x^2e^{2x} = 2xe^{2x}.
$$
The coefficients of the latter function are indeed as you conjectured.
