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