Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 6

up vote 8 down vote accepted

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

share|improve this answer
1  
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
1  
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
1  
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)!}$$

share|improve this answer

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.

share|improve this answer
    
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)!}\;. $$

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.