A while back I found the series $$\sum_{k=0}^n \binom n k (-1)^k (x+k)^n = (-1)^n n!$$ while messing around in Algebra class (specifically when $n$ is any natural number and $x$ is any real number) I wrote the formula on a card, stuck it in my "to prove" box. The formula arises when subtracting subsequent powers of natural natural numbers, I.e. We start with $1^2, 2^2, 3^2, 4^2...$ and subtract subsequent terms, getting $3,5,7...$ and repeat, getting $2,2,2... = 2!$. Its well known that it takes $n$ steps using this process to get to a constant using the sequence $1^n,2^n...$, so I assume that this should be a well known theorem. I found the series written exactly like this on the OEIS, but not link was provided I could find. I have tried a number of series manipulations, but none yielded anything prettier than I started with. I considered letting $x=0$ and proving it from there (as this simplifies things), but I still couldn't quite get it. Does anyone know a proof of this using relatively elementary techniques?
-
The right side doesn't depend on $x$? I'd think it would? Or is there a whole lot of cancellation that happens? – John Feb 05 '16 at 19:01
-
@John you are correct; the series should work for all values of $x$, at least all real values (it arises naturally in the way I found the series). Now, don't ask me WHY that works... It simply seems to work numerically for every value of $x$ I use :/ – Brevan Ellefsen Feb 05 '16 at 19:16
-
The related formula $$\sum_{k = 0}^{n} (-1)^{n - k}\binom{n}{k}k^n = n!$$ counts bijections from a set with $n$ elements to itself. – N. F. Taussig Feb 05 '16 at 19:23
-
@N.F.Taussig intersting, thank you! This answers the question for $x=0$. Any ideas on how to show this works for any real $x$? – Brevan Ellefsen Feb 05 '16 at 19:26
-
@BrevanEllefsen Alas, no. – N. F. Taussig Feb 05 '16 at 19:27
-
@N.F.Taussig hmm.. Oh well. Your input remains useful nonetheless! I could use induction to get the weaker form for natural numbers $x$ using the series you give, but real $x$ eludes me... – Brevan Ellefsen Feb 05 '16 at 19:33
2 Answers
The identity you're seeking is closely related to finite differences. The finite differences $\Delta^1f, \Delta^2f, \Delta^3f,\ldots$ of a function $f$ are defined inductively as $$(\Delta^1f)(x) := f(x+1) -f(x)$$ and $$(\Delta^{n+1}f)(x) := \Delta^1(\Delta^nf)(x), $$ i.e. the $(n+1)$st finite difference of $f$ is the first finite difference of the $n$th finite difference of $f$, etc. As an aside, this leads to the alternative form $$ (\Delta^nf)(x) = \sum_{k=0}^n{n\choose k}(-1)^{n-k}f(x+k)\tag1 $$ which you can prove by induction.
In view of (1), the identity you're trying to prove amounts to the assertion
Claim: If $f_n(x):=x^n$, then $\Delta^nf_n$ is identically constant at $n!$.
You can prove this by induction. The case $n=1$ is clear. Suppose the claim holds for $n$. Using the Leibniz rule for the finite difference of a product (taking $\Delta^0f:=f$): $$ (\Delta^n[fg])(x) = \sum_{k=0}^n{n\choose k}(\Delta^kf)(x)(\Delta^{n-k}g)(x+k), $$ we write: $$ (\Delta^{n+1}f_{n+1})(x) =(\Delta^{n+1}[f_nf_1])(x)=\sum_{k=0}^n{n+1\choose k}(\Delta^kf_n)(x)(\Delta^{n+1-k}f_1)(x+k).$$ Since $\Delta^1f_1$ is identically equal to $1$, and $\Delta^if_1 = 0$ for $i>1$, the summation above reduces to two terms: $k=n$ and $k=n+1$, giving $$ {n+1\choose n}(\Delta^nf_n)(x)\cdot 1 + {n+1\choose n+1}(\Delta^{n+1}f_n)(x)\cdot (x+k)=(n+1)! $$ since $\Delta^nf_n=n!$ by hypothesis, which implies $\Delta^{n+1}f_n=\Delta^1(\Delta^nf_n)=0$.
- 38,951
-
Wow. While this is a little more complex than what I was hoping for, this is a pretty amazing solution – Brevan Ellefsen Feb 05 '16 at 20:56
so we would need to show that for all $j$ such that $n\ge j\gt0$ $$\sum_{k=0}^n \binom n k \binom n j (-1)^k (k)^{n-j} = 0$$ that is $$\sum_{k=0}^n \binom n k (-1)^k (k)^{n-j} = 0$$ this involves a Stirling number of second kind $$\sum_{k=0}^n \binom n k (-1)^k (k)^{n-j} =(-1)^n (n!){n-j\brace n}$$ which is $0$ since $j\gt0$
- 3,716
-
What are you proving above?? I fail to see the connection... And are you solving for the series when $x=0$? – Brevan Ellefsen Feb 05 '16 at 19:36
-
The proof for $x=0$ is given in N.F. Taussig's comment. I just did the binomial development of $(x+k)^n$ in your series and tried to explain that each coefficient before $x^j$ is $0$ provided that $j$ is not $0$ – René Gy Feb 05 '16 at 19:42
-
Ah, after working this out on paper and filling in a few steps I see what you're saying. However, do you know an alternate proof of the final claim?? It's not that I'm not familiar with the Stirling numbers, I just wanted a proof as elementary as possible. This is a wonderful observation though, and answers my question! I will accept accordingly. – Brevan Ellefsen Feb 05 '16 at 20:02
-
I believe that $$\sum_{k=0}^n \binom n k (-1)^k (k)^{n-j} = 0$$ should have a proof by induction, from $j=n$ which is well known, then backward down to $j=1$, by using the usual recursion for binomial coefficient. – René Gy Feb 05 '16 at 20:19