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.

In How to integrate $\int x^n e^x dx$?, it is shown that

$$\int {x^n e^x dx} = e^x \sum_{k = 0}^n ( - 1)^k \frac{n!}{(n-k)!}x^{n-k} + C.$$

Since $\frac{n!}{(n-k)!}$ is $P(n,k)$, the number of $k$-permutations of $n$ objects, the right-hand side of this formula smells like the inclusion-exclusion principle to me. In fact, the right-hand side is almost the formula for the number of derangements on $n$ elements, which is one of the classic examples of the use of the inclusion-exclusion principle.

This would seem to imply that there is some way to interpret $\int x^n e^x dx$ combinatorially such that the right-hand side formula falls out immediately. However, I haven't been able to see it. (I don't even know much about combinatorial interpretations of indefinite integration - or even if there are known ways to do so in special cases like this one.)

Does anyone know or see a way to prove $$\int {x^n e^x dx} = e^x \sum_{k = 0}^n ( - 1)^k \frac{n!}{(n-k)!}x^{n-k} + C$$ combinatorially?

Added: To clarify, I am looking for a proof that shows that the left- and right-hand sides of the formula count the same thing. That, to me, is a combinatorial proof.

share|improve this question
1  
If you write out the power series for the left and right sides, you will probably get an identity for the coefficient of $x^j$ that can be proven combinatorially. –  Jim Belk Jun 21 '11 at 16:42
4  
See also: wellesley.edu/Math/pdffiles.d/kayll-colloq.pdf –  Aryabhata Jun 21 '11 at 18:28
    
@Aryabhata: Interesting. –  Eric Naslund Jun 21 '11 at 18:43

4 Answers 4

up vote 11 down vote accepted

Here is a solution I quite like which uses inclusion exclusion on a integral over an $n$-dimensional simplex.

First, it is much nicer to consider the definite integral $\int_0^x y^n e^{y} dy$ which will only be off by a constant. (Which we don't care about anyway)

Consider

$$\int_{0}^{x}\int_{0}^{t_{1}}\cdots\int_{0}^{t_{n}}e^{-t_{n+1}}dt_{n+1}dt_{n}\cdots dt_{1}.$$

This is $e^{-t_{n+1}}$ integrated over the $n$-dimesional simplex. (Only one coordinate is integrated) By Cauchy's formula for repeated integration, this is the same as $$\frac{1}{n!}\int_{0}^{x}(x-y)^{n}e^{-y}dy=\frac{1}{n!}e^{-x}\int_{0}^{x}y{}^{n}e^{y}dy.$$ Now, we need only show that $$\int_{0}^{x}\int_{0}^{t_{1}}\cdots\int_{0}^{t_{n}}e^{x-t_{n+1}}dt_{n+1}dt_{n}\cdots dt_{1}=e^{x}\sum_{k=0}^{n}\frac{(-1)^{n-k}}{k!}x^{k}+C.$$ (A constant will arise since the integrand is not $0$ at $0$) But this follows from splitting up the simplex and using inclusion exclusion. Here is why: Integrating $e^{x-t_1}$ over the cube gives $x^ke^x$. Since the cube can be divided into $k!$ simplicies we get $\frac{x^k}{k!}e^x$. Now we need to subtract off a correction factor based on the $n-1$-dimensional simplicies, and so on.

Hope that helps,

share|improve this answer

Though it is probably not what you are looking for, I find it relevant to give the following very simple derivation. So we actually want to prove $$ \frac{d}{{dx}}e^x \sum\limits_{k = 0}^n {( - 1)^k \frac{{n!}}{{(n - k)!}}x^{n - k} } = x^n e^x . $$ By the product rule, the left-hand side is given by $$ e^x \sum\limits_{k = 0}^n {( - 1)^k \frac{{n!}}{{(n - k)!}}x^{n - k} } + e^x \sum\limits_{k = 0}^{n - 1} {( - 1)^k \frac{{n!}}{{(n - k)!}}} (n - k)x^{n - k - 1} , $$ or $$ e^x \bigg(x^n + \sum\limits_{k = 1}^n {( - 1)^k \frac{{n!}}{{(n - k)!}}x^{n - k} } + \sum\limits_{k = 0}^{n - 1} {( - 1)^k \frac{{n!}}{{(n - k - 1)!}}x^{n - k - 1} \bigg)} , $$ or $$ e^x \bigg(x^n + \sum\limits_{k = 1}^n {( - 1)^k \frac{{n!}}{{(n - k)!}}x^{n - k} } + \sum\limits_{k = 1}^n {( - 1)^{k - 1} \frac{{n!}}{{(n - k)!}}x^{n - k} \bigg)} , $$ hence by $$ e^x x^n. $$

share|improve this answer
    
As you say, this is not really what I am looking for. I would like to see a combinatorial proof. –  Mike Spivey Jun 21 '11 at 21:22
    
It is a nice and direct non-combinatorial proof, though. –  Mike Spivey Jun 21 '11 at 21:38
    
Thanks. (It was worth posting it in view of the various proofs already given -- here and in the related post.) –  Shai Covo Jun 21 '11 at 21:59

Depends what you mean by "combinatorics." Does more analytic combinatorics and exponential generating series count? Lets look at the definite integral $\int_0^x y^ne^y dy$ instead of $\int x^ne^xdx$

Let $a_n=\int_0^x y^n e^y$. Then $$\sum_{n=0}^{\infty}a_{n}\frac{z^{n}}{n!}=\int_0^x e^{zy+y}dy=\frac{1}{\left(z+1\right)}e^{(z+1)x}-1=e^{x}\left(e^{zx}\left(1+z\right)^{-1}\right)-1.$$

Taking the product of power series we have

$$e^{x}\left(1+zx+\frac{\left(zx\right)^{2}}{2!}+\frac{(zx)^{3}}{3!}\cdots\right)\left(1-z+z^{2}-z^{3}+z^{4}+\cdots\right)-1.$$

$$=e^{x}\left(\sum_{n=1}^{\infty}\left(\sum_{k=0}^{n}(-1)^{n-k}\frac{x^{k}}{k!}\right)z^{n}\right)-1$$ and hence by comparing coefficients we conclude $$\int x^{n}e^{x}dx=n!e^x\sum_{k=0}^{n}(-1)^{n-k}\frac{x^{k}}{k!}+C.$$

Maybe that helps,

share|improve this answer
1  
You missed out on a factor of $e^x$ on the right hand side. –  user17762 Jun 21 '11 at 17:21

I managed to find a simple probability argument that's in the spirit of what I was looking for.

First, do a variable switch, with $t = -x$: $\int x^n e^x dx = (-1)^{n+1} \int t^n e^{-t} dt$.

Now, consider the definite version of the second integral, with an extra factor of $\frac{1}{n!}$: $$\int_0^T \frac{t^n e^{-t}}{n!} dt.$$ This is the probability that the sum of $n+1$ independent exponential(1) random variables (which has an Erlang (or gamma) distribution) is less than $T$.

Since interarrival times in a Poisson process are independent and exponentially distributed, this is also the probability that at least $n+1$ events have occurred by time $T$ in a Poisson process with rate 1. If $N(T)$ denotes the number of events that occur in $[0,T]$ in a Poisson(1) process, we know that $P(N(T) = k) = T^k e^{-T}/k!$. Thus $$\int_0^T \frac{t^n e^{-t}}{n!} dt = P(N(T) \geq n+1) = 1 - P(N(T) \leq n) = 1 - \sum_{k=0}^n P(N(T) = k) = 1 - \sum_{k=0}^n \frac{T^k}{k!} e^{-T}.$$ Switching back in terms of $x$ and multiplying through by $n!$, we have
$$\int x^n e^x dx = - (-1)^{n+1} \sum_{k=0}^n \frac{n!}{k!} (-x)^ke^x +C = e^x \sum_{k=0}^n (-1)^{n-k} \frac{n!}{k!}x^k +C$$ $$= e^x \sum_{k=0}^n (-1)^k \frac{n!}{(n-k)!}x^{n-k} + C.$$

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.