1
$\begingroup$

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.

  • 1
    The _denominator_ here should look like something you've seen before.2011-09-29

2 Answers 2

4

$\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)

  • 0
    That's probably a bit tougher. I recommend you ask that as a separate question.2011-09-29
3

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.