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.

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.

share|improve this question
    
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
1  
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}$. –  kigen Jan 14 '13 at 7:24

4 Answers 4

up vote 3 down vote accepted

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*}

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

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

share|improve this answer

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

share|improve this answer

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

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.