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

-
Are you interested only in an algebraic derivation of the later expression from the sum, or perhaps a probabilistic proof will suite as well? Because there's a short proof uses the interpretation you mentioned of the sum, but you may already know it. –  Ofir Dec 15 '12 at 1:47
@Ofir I was interested in the algebraic derivation. So the answers given here were just right (and your extra info very interesting btw.). Wrt the probabilistic argument: I guess you refer to the inductive proof D^2(1) = 1, D^2(N) = D^2(N-1)+1 where D^2(N) is the square of the average final position after a random walk of N steps, right? –  jerico Dec 15 '12 at 1:59
Yep, that's the proof I had in mind. Shorter than everything else :) –  Ofir Dec 26 '12 at 0:44

## 6 Answers

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

-
It's actually easier to prove (3'): $\sum n(n-1)\binom N n = N(N-1) 2^{N-2}$, and then write $$(N-2n)^2 = N^2 - (4N-4)n + 4n(n-1)$$ –  Thomas Andrews Dec 14 '12 at 20:38
You're right and this is evident by step 2 in my generalization. But I wanted to solve the original problem in a straightforward manner so that it won't look tricky or difficult. –  Ofir Dec 14 '12 at 20:57
Thanks for pointing out the general case! –  jerico Dec 14 '12 at 21:00
Isn't the general case that $\sum_k P(n,k) \binom{n}{k} = Q(n)2^{n}$ for some polynomial $Q$? There is no unbound $k$ on the left side. –  Thomas Andrews Dec 14 '12 at 21:12
Specifically, all polynomials, $P(n,k)$ can be written as $$P(n,k)=\sum_{i=0}^d P_i(n) \binom {k}{i}$$ For some sequence of polynomials $P_i$. Then $$Q(n)=\sum_{i=0}^d P_i(n) \binom{n}{i} 2^{-i}$$ –  Thomas Andrews Dec 14 '12 at 21:21

$$(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.

-
I think the last line should say $x=1$? –  joriki Dec 14 '12 at 20:32
Thanks. I will edit it. –  Amr Dec 14 '12 at 20:33

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

-

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.

-

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.

-