simplify summation of factorial (random walk)
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...
$$(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)!}$$
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.