# summation identity - statistics

What does this summation simplify to?

$$\sum_{x=0}^{y} \frac{1}{x!(y-x)!}$$

I tried applying common formulas (Maclaurin series, binomial coefficients, etc. but nothing seems to match up to it).

Any tips would be appreciated.

Thanks.

-
The denominator here should look like something you've seen before. –  Michael Hardy Sep 29 '11 at 0:42

$$\sum_{x=0}^y\frac{1}{x!(y-x)!}=\frac{1}{y!}\sum_{x=0}^y\frac{y!}{x!(y-x)!}=\frac{1}{y!}\sum_{x=0}^y\binom{y}{x}=\frac{2^y}{y!}$$ (see here and here)

-
What if it was the same summation except it was x * (y choose x)? –  icobes Sep 29 '11 at 0:47
That's probably a bit tougher. I recommend you ask that as a separate question. –  Zev Chonoles Sep 29 '11 at 0:48

To supplement Zev's elegant and direct answer, I would find the sum using generating functions technique.

Lemma: Let $\phi(t)$ be the generating function of $\{a_k\}$ sequence, i.e. $\phi(t) = \sum_{k=0}^\infty a_k t^k$ (treated as a formal sum), and $\psi(t)$ be the generating function corresponding to $\{b_k\}$ sequence. Then $$\phi(t) \psi(t) = \sum_{n=0}^\infty t^n \left( \sum_{k=0}^n a_k b_{n-k}\right)$$ Proof: $$\phi(t) \psi(t) = \sum_{k=0}^\infty \sum_{m=0}^\infty a_k b_m t^{k+m} \left. =\right\vert_{n = k+m} \sum_{n=0}^\infty t^n \sum_{k=0}^\infty \sum_{m=0}^\infty \delta_{n, k+m} a_k b_m = \sum_{n=0}^\infty t^n \left( \sum_{k=0}^n a_k b_{n-k} \right)$$ Q.E.D.

Now for the sequence at hand, $\phi(t) = \exp(t) = \sum_{k=0}^\infty t^k \frac{1}{k!}$, and on one hand: $$\phi(t) \phi(t) = \exp(2 t) = \sum_{n=0}^\infty \frac{2^n}{n!} t^n$$ but on another, using the lemma $\phi(t)^2 = \sum_{n=0}^\infty t^n \sum_{k=0}^n \frac{1}{k!} \frac{1}{(n-k)!}$. Comparing coefficients, the result follows.

-