# Combinatorial proof

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

-
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

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}

-

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

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

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

-