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.

Using notion of derivative of functions from Taylor formula follow that

$$e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}$$

Is there any elementary combinatorial proof of this formula

here is my proof for $x$ natural number

Denote by $P_k^m$ number of $k$-permutations with unlimited repetitions of elements from a $m$-set then we can prove that $$P_k^m=\sum_{r_0+r_1+...+r_{m-1}=k}\frac{k!}{r_0 !...r_{m-1}!}$$ also is valid $$P_k^m=m^k$$ Based on first formula we can derive that $$\sum_{k=0}^{\infty}P_k^m\frac{x^k}{k!}=\left(\sum_{k=0}^{\infty}\frac{x^k}{k!}\right)^m$$ from second formula $$\sum_{k=0}^{\infty}P_k^m\frac{x^k}{k!}=\sum_{k=0}^{\infty}\frac{(mx)^k}{k!}$$ now is clear that $$\sum_{k=0}^{\infty}\frac{(mx)^k}{k!}=\left(\sum_{k=0}^{\infty}\frac{x^k}{k!}\right)^m$$ from last equation for $x=1$ taking in account that $$\sum_{k=0}^{\infty}\frac{1}{k!}=e=2,71828...$$ we have finally that for natural number $m$ is valid formula $$e^m=\sum_{k=0}^{\infty}\frac{m^k}{k!}$$

share|improve this question
7  
What definition of $e^x$ are you working from? Perhaps math.stackexchange.com/questions/3507/… is what you're looking for? –  Qiaochu Yuan Jul 29 '11 at 13:49
    
Do you need a proof for the formula in general or a proof with taylor or do you need the limit? –  ulead86 Jul 29 '11 at 14:05
    
In my question I suppose that x is real number. If x is natural number I can prove combinatorialy that formula works. –  Adi Dani Jul 29 '11 at 14:31
    
@Adi: oh, I see, you're defining $e = \sum \frac{1}{k!}$ and you want to show that $e^x = \sum \frac{x^k}{k!}$. Well, I am pretty sure that if two formal power series are equal for all non-negative integers then they are already identical, so... –  Qiaochu Yuan Jul 29 '11 at 15:16
    
@Qiaochu, perhaps I'm misunderstanding you, but the power series for $\sin\pi x$ and $-\sin\pi x$ are equal for all integers but not identical. –  Gerry Myerson Jul 29 '11 at 23:07

4 Answers 4

up vote 6 down vote accepted

We will handle $x>0$ here.

If we define $e=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n$, then $e^x=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{nx}$. Note that since $0\le nx-\lfloor nx\rfloor<1$, $$ \begin{align} e^x&=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{nx}\\ &=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{\lfloor nx\rfloor} \left(1+\frac{1}{n}\right)^{nx-\lfloor nx\rfloor}\\ &=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{\lfloor nx\rfloor} \lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{nx-\lfloor nx\rfloor}\\ &=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{\lfloor nx\rfloor} \end{align} $$ Using the binomial theorem, $$ \begin{align} \left(1+\frac{1}{n}\right)^{\lfloor nx\rfloor} &=\sum_{k=0}^{\lfloor nx\rfloor} \frac{1}{k!}\frac{P({\lfloor nx\rfloor},k)}{n^k}\\ &=\sum_{k=0}^\infty \frac{1}{k!}\frac{P({\lfloor nx\rfloor},k)}{n^k} \end{align} $$ Where $P(n,k)=n(n-1)(n-2)...(n-k+1)$ is the number of permutations of $n$ things taken $k$ at a time.

Note that $0\le\frac{P({\lfloor nx\rfloor},k)}{n^k}\le x^k$ and that $\sum_{k=0}^\infty \frac{x^k}{k!}$ converges absolutely. Thus, if we choose an $\epsilon>0$, we can find an $N$ large enough so that, for all $n$, $$ 0\le\sum_{k=N}^\infty \frac{1}{k!}\left(x^k-\frac{P({\lfloor nx\rfloor},k)}{n^k}\right)\le\frac{\epsilon}{2} $$ Furthermore, note that $\lim_{n\to\infty}\frac{P({\lfloor nx\rfloor},k)}{n^k}=x^k$. Therefore, we can choose an $n$ large enough so that $$ 0\le\sum_{k=0}^{N-1} \frac{1}{k!}\left(x^k-\frac{P({\lfloor nx\rfloor},k)}{n^k}\right)\le\frac{\epsilon}{2} $$ Thus, for n large enough, $$ 0\le\sum_{k=0}^\infty \frac{1}{k!}\left(x^k-\frac{P({\lfloor nx\rfloor},k)}{n^k}\right)\le\epsilon $$ Therefore, $$ \lim_{n\to\infty}\;\sum_{k=0}^\infty\frac{1}{k!}\frac{P({\lfloor nx\rfloor},k)}{n^k}=\sum_{k=0}^\infty\frac{x^k}{k!} $$ Summarizing, we have $$ \begin{align} e^x&=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{nx}\\ &=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{\lfloor nx\rfloor}\\ &=\lim_{n\to\infty}\;\sum_{k=0}^\infty \frac{1}{k!}\frac{P({\lfloor nx\rfloor},k)}{n^k}\\ &=\sum_{k=0}^\infty\frac{x^k}{k!} \end{align} $$

share|improve this answer
    
Another missed Bezout opportunity. Your bezoukas must be getting rust! –  Bill Dubuque Feb 25 at 21:16
    
@BillDubuque: I went for more recent fodder. –  robjohn Feb 25 at 21:40

Fact: Every nonzero continuous function $F\colon\mathbb R\to\mathbb R_+$ where $F(a+b)=F(a)F(b)$ is an exponential function for some base: $F(x)=a^x$. To prove this, first note that $F(0)=F(0+0)=F(0)F(0)$. So $F(0)^2=F(0)$. So $F(0)\in\{0,1\}$. But if $F(0)=0$, the whole function is identically zero. Now let $a=F(1)$ and first prove this for positive integers $x=n$: $F(n)=F(1+\cdots+1)=F(1)\cdots F(1)=a^n$. Extend to negative integers using $1=F(0)=F(n-n)=F(n)F(-n)=a^nF(-n)$. So $F(-n)=a^{-n}$. Now extend to rationals $x=p/q$: $a^p=F(p)=F(q\cdot p/q)=F(p/q)^q$. So $F(p/q)=a^{p/q}$. To extend to all reals, we invoke continuity. Given a real $r$, find a sequence of rationals that converge to it $q_n\to r$. Then $F(r)=\lim_{n\to\infty}F(q_n)=\lim_{n\to\infty}a^{q_n}=a^r$. This last step was not combinatorial, so I am cheating.

Now you can combinatorially prove that if you let $F(x)=\sum_{n=0}^\infty \frac{x^n}{n!}$, then $F(a+b)=F(a)F(b)$. So $F(x)=a^x$ for some $a>0$. Now you just need to show $a=e$. This will depend on how you defined $e$ in the first place. I'll assume $e=\lim_{n\to\infty}(1+1/n)^n$. Apply the binomial theorem to $(1+1/n)^n$ to get $$(1+1/n)^n=\sum_{k=0}^n \binom{n}{k}n^{-k}=1+n/n+\frac{n(n-1)}{2n^2}+\cdots$$ This is approximately $1+1+\frac{1}{2}+\frac{1}{3!}+\cdots.$ Taking the limit as $n$ goes to infinity, we get $e=\sum_{k=0}^\infty \frac{x^k}{k!}$. (This step can be made rigorous. I've given a sketch.) But $F(1)=a^1$ matches this expression, so $a=e$.

share|improve this answer
1  
By the way, the real numbers are not defined combinatorially, so it may be that there is no completely combinatorial proof. –  Grumpy Parsnip Jul 29 '11 at 18:23

I don't know if this is what you are looking for, but working from the fact that $\frac{d}{dx}e^x=e^x$, we can say that if $$ e^x=\sum_{k=0}^\infty\;a_k\;x^k $$ then, by taking the derivative of both sides, we get $$ \begin{align} e^x&=\sum_{k=1}^\infty\;k\;a_k\;x^{k-1}\\ &=\sum_{k=0}^\infty\;(k+1)\;a_{k+1}\;x^k \end{align} $$ Equating the coefficients of $x^k$ in these two formulas for $e^x$, we get that $a_k=\frac{1}{k}\;a_{k-1}$. Since $e^0=1$, we have that $a_0=1$. Thus, we are lead to the conclusion that $a_k=\frac{1}{k!}$. That is, $$ e^x=\sum_{k=0}^\infty\frac{x^k}{k!} $$

share|improve this answer
    
My question is without using derivatives –  Adi Dani Jul 29 '11 at 14:53
    
@Adi: Can you modify your question then? (there is a combinatorial interpretation of the derivative, but it may not be appropriate here because the question is not the usual way of interpreting $e^x$ combinatorially) –  Mitch Jul 29 '11 at 20:36

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ Assume you flip $N$ times a coin. Assume that he probability to have tail is $x/N$ and head is $1 - x/N$. The probability of $k$ tails is $$ {N \choose k}\pars{x \over N}^{k}\pars{1 - {x \over N}}^{N - k} $$ The probability of "no tails" or $1$ tail or $2$ tails $\ldots$ or $N$ tails is obviously equal to $1$. Namely: $$ \sum_{k = 0}^{N}{N \choose k}\pars{x \over N}^{k}\pars{1 - {x \over N}}^{N - k} =1 $$ Now, take the limit $N \to \infty$ ( a delicate and exquisit one !!! ) and the result is: $$ \expo{-x}\sum_{k = 0}^{\infty}{x^{k} \over k!}=1 $$

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.