Combinatorial proof: $e^x=\sum\limits_{k=0}^{\infty}\frac{x^k}{k!}$

Question

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

Answer 1

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

Answer 2

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

Answer 3

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