simplify summation of factorial (random walk)

Question

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.)

Answer 1

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):

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

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

3. $\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...

Answer 2

$$(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)!}$$

Answer 3

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.

Answer 4

$$ \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)!}\;. $$

Answer 5

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.

Answer 6

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.