# prove $s(x+y)=s(x)s(y)$

I am asked to prove the following:

Let $s(x):=\sum_{n=0}^{\infty}\binom{x}{n}$. Then $s(x+y)=s(x)s(y)$.

I don't know how to start. I am thinking about $\exp(x)$ function with $\sum_{n=0}^{\infty}\dfrac{x^n}{n!}$. Am I okay with this start? I would then begin like this: $$\sum_{n=0}^{n}\dfrac{x^n}{n!} \cdot \dfrac{y^n}{n!} = .. help = \frac{1}{n!}(x+y)^n$$

I am not sure how to continue or whether I am okay.

Thanks for help.

-
What is $s(x)$? –  Michael Albanese Jan 14 '13 at 6:53
Is $s(x) = \exp(x)$? –  user17762 Jan 14 '13 at 6:54
you can't prove something that is not correct. Unless there are some restrictions on $s$ the statement is false. –  Amihai Zivan Jan 14 '13 at 6:54
oh yeah, sorry, i missed one definition - please see my Update –  doniyor Jan 14 '13 at 7:00
I believe the 3 answers regarding the exponential function have not yet read the update; I have posted an answer addressing $s(x)=\sum \binom{x}{n}$. –  neuguy Jan 14 '13 at 7:24

First you must observe that the series converges absolutely. Then we can use the fact that $\sum a_{n}b_{n}=AB$ if $\sum a_{n}=A$ and $\sum b_{n}=B$ and at least one of the series is absolutely convergent. With this, we compute: \begin{align*} s(x)s(y) &=\sum_{n=0}^{\infty}\frac{x^{n}}{n!}\sum_{m=0}^{\infty}\frac{y^{n}}{n!}\\ &=\sum_{n=0}^{\infty}\sum_{j=0}^{n}\frac{x^{j}y^{n-j}}{j!(n-j)!}\\ &=\sum_{n=0}^{\infty}\frac{1}{n!}\sum_{j=0}^{n}\binom{n}{j}x^{j}y^{n-j}\\ &=\sum_{n=0}^{\infty}\frac{(x+y)^{n}}{n!}\\ &=s(x+y). \end{align*}

-
Thanks, Jtitan, –  doniyor Jan 14 '13 at 7:14
can you please explain me how this steps arises: $\sum_{n=0}^{\infty}\sum_{j=0}^{n}\dfrac{x^{j}y^{n-j}}{j!(n-j)!}$ –  doniyor Jan 14 '13 at 7:17

We have the generalized binomial theorem

$$(1+z)^x= \sum_{n=0}^\infty \binom{x}{n}z^n$$

where $\binom{x}{n}$ denotes the generalized binomial coefficient

$$\binom{x}{n} = \frac{x(x-1)(x-2)\cdot\ldots\cdot(x-n+1)}{n}$$

Provided $x > -1$, this series converges with radius of convergence $1$, and specifically for $z=1$; convergence at $z=1$ is absolute if and only if $x > 0$. Thus, assuming $x > 0$, we have $s(x)=(1+1)^x=2^x$, and now the problem is trivial: $$s(x)s(y)=2^x2^y=2^{x+y}=s(x+y)$$ for $x,y>0$.

-

$$\exp(x) \exp(y) = \left(\sum_{m=0}^{\infty} \dfrac{x^m}{m!}\right)\left(\sum_{n=0}^{\infty} \dfrac{y^n}{n!}\right) = \sum_{m=0}^{\infty}\sum_{n=0}^{\infty} \dfrac{x^m}{m!}\dfrac{y^n}{n!}\\ = \sum_{k=0}^{\infty} \sum_{m+n=k} \dfrac{x^m}{m!}\dfrac{y^n}{n!} = \sum_{k=0}^{\infty} \sum_{n=0}^k \dfrac{x^{k-n}}{(k-n)!}\dfrac{y^n}{n!}$$ Now note that $$\dfrac{x^{k-n}}{(k-n)!}\dfrac{y^n}{n!} = \dfrac1{k!} \dbinom{k}n x^{k-n} y^n$$ Hence, we get that $$\exp(x) \exp(y) = \underbrace{\sum_{k=0}^{\infty} \dfrac1{k!} \sum_{n=0}^k \dbinom{k}n x^{k-n} y^n = \sum_{k=0}^{\infty} \dfrac{(x+y)^k}{k!}}_{\text{Using binomial theorem}} = \exp(x+y)$$

EDIT

Answering the updated question. First note the following combinatorial identity.

$$\dbinom{x+y}k = \sum_{n=0}^k \dbinom{x}n \dbinom{y}{k-n} \,\,\,\,\,\,\,\,\,\,\,\, (\star)$$ Hence, $$s(x+y) = \sum_{k=0}^{\infty} \dbinom{x+y}k = \sum_{k=0}^{\infty}\sum_{n=0}^k \dbinom{x}n \dbinom{y}{k-n} = \sum_{k=0}^{\infty}\sum_{m+n=k} \dbinom{x}n \dbinom{y}{m}\\ = \sum_{m=0}^{\infty}\sum_{n=0}^{\infty} \dbinom{x}n \dbinom{y}{m} = \left(\sum_{n=0}^{\infty} \dbinom{x}n\right) \left(\sum_{m=0}^{\infty} \dbinom{y}{m} \right) = s(x) s(y)$$

If $x,y \in \mathbb{N}$, there is a nice combinatorial proof for $(\star)$. Consider a bag with $x$ red balls and $y$ blue balls. We want to choose a total of $k$ balls from these two bags. Hence, the number of ways of doing this is $\dbinom{x+y}k$. We can also count this by another method. Choose $n$ red balls and $k-n$ blue balls. The number of ways is $\dbinom{x}n \dbinom{y}{k-n}$. Now $n$ can vary from $0$ to $k$. Hence, the total number of ways of choosing $k$ balls from both these bags is $\displaystyle \sum_{k=0}^n \dbinom{x}n \dbinom{y}{k-n}$. Hence, we get that $$\dbinom{x+y}k = \sum_{n=0}^k \dbinom{x}n \dbinom{y}{k-n}$$

-

Probably something like

$$\sum_{n=0}^\infty \frac{(x+y)^n}{n!}=\sum_{n=0}^\infty\sum_{i=0}^n \frac{1}{n!}\binom{n}{i}x^iy^{n-i}=\sum_{n=0}^\infty \sum_{i=0}^n \frac{x^i}{i!}\frac{y^{n-i}}{(n-i)!}=\left(\sum_{j=0}^\infty \frac{x^j}{j!}\right)\left(\sum_{k=0}^\infty \frac{y^k}{k!}\right).$$

-