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.

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.

share|improve this question
1  
The denominator here should look like something you've seen before. –  Michael Hardy Sep 29 '11 at 0:42

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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.

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.