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.

Basically I had some fun doing this:

0
    1
1       6
    7       6
8       12
    19      6
27      18
    37      6
64      24
    61
125

etc.

starting with $k^n$ ($n=3$) and then calculating the differences. It turns out that the result after n steps is always $n!$. Pretty neat, heh? :)

Therefore:

$$ n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $$ where $n \in \mathbb{N}$ and $r \in \mathbb{Z}$

But how do I prove that?

share|improve this question
    
any integer $r$ ? –  Belgi Sep 23 '12 at 20:08
    
Can you please explain where the RHS has come from? –  Daniel Littlewood Sep 23 '12 at 20:08
    
@Belgi Yes, I believe so. –  Alex Sep 23 '12 at 20:08
    
@DanLitt basically looking what's happening with the numbers on the left. Just use a,b,c,d and calculate the differences of them. –  Alex Sep 23 '12 at 20:10
    
So you want to know why the difference always comes out to $n!$? –  Daniel Littlewood Sep 23 '12 at 20:11

4 Answers 4

up vote 14 down vote accepted

Let $\mathbf E$ be the shift operator on functions on $\Bbb R$ or $\Bbb Z$: $(\mathbf{E}f)(x)=f(x+1)$. Let $\mathbf\Delta$ be the forward difference operator: $(\mathbf{\Delta} f)(x)=f(x+1)-f(x)$. Let $\mathbf 1$ be the identity operator: $\mathbf{1}f=f$. Then $\mathbf{\Delta}=\mathbf{E}-\mathbf{1}$, so $$\mathbf{\Delta}^n=(\mathbf{E}-\mathbf{1})^n=\sum_{k=0}^n(-1)^k\binom{n}k\mathbf{E}^{n-k}\;,$$ and therefore

$$\begin{align*} \mathbf{\Delta}^nf(r)&=\sum_{k=0}^n(-1)^k\binom{n}k\mathbf{E}^{n-k}f(r)\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}kf(r+n-k)\;. \end{align*}$$

In particular, if $f(x)=x^n$, we have

$$\mathbf{\Delta}^nf(r)=\sum_{k=0}^n(-1)^{n-k}\binom{n}k(r+n-k)^n\;.\tag{1}$$

Now I claim that $\mathbf{\Delta}^nf$ is the constant function with value $n!$. This is easy to prove by induction. Suppose that it’s true for all exponents less than $n$, and note that if $f$ is a constant function, then $\mathbf{\Delta}^kf$ is identically $0$ for all $k\ge 1$. Then

$$\mathbf{\Delta}x^n=(x+1)^n-x^n=\sum_{k=0}^{n-1}\binom{n}kx^k$$ by the binomial theorem, so

$$\begin{align*} \mathbf{\Delta}^nx^n&=\sum_{k=0}^{n-1}\binom{n}k\mathbf{\Delta}^{n-1}x^k\\ &=\binom{n}{n-1}(n-1)!\\\\ &=n(n-1)!\\\\ &=n!\;, \end{align*}$$

and the induction is complete. Combining this with $(1)$ yields the desired result.

share|improve this answer

Suppose $f(x)=a_0 x^n+a_1x^{n-1}+\ldots+a_n$ be a polynomial of degree $n$. It is straightforward to check that $f(x+1)-f(x)$ is a polynomial in $x$ of degree $n-1$, with leading coefficient $n a_0$. Taking $f(x)=x^n$ and repeating this process $n$ times, we get that $$ \sum_{k=0}^n (-1)^k {n\choose k}(x+n-k)^n $$ is a polynomial in $x$ of degree 0, with leading coefficient $n!$.

share|improve this answer

Let $D = \partial/\partial x$. Then $$\begin{eqnarray*} \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} &=& \sum_{k=0}^{n}(-1)^{n-k} \binom{n}{k}(k+r)^{n} \\ &=& \left.\left(x D\right)^n \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} x^{k+r}\right|_{x=1} \\ &=& \left.\left(x D\right)^n x^r(x-1)^n \right|_{x=1} \\ &=& \left.D^n (x-1)^n\right|_{x=1} \\ &=& n! \end{eqnarray*}$$

Notice that in the evaluation of $\left.\left(x D\right)^n x^r(x-1)^n \right|_{x=1}$, all contributions of the form $x^m D^m x^r(x-1)^n$ with $m<n$ vanish. For more on the operator $(x D)^n$, see this question.

share|improve this answer

Since the question is tagged "combinatorics," here's a combinatorial proof. :)

Let $A_k$ be the set of all functions $f: \{1, 2, \ldots, n\} \mapsto \{1, 2, \ldots, n+r\}$ such that $f(i) = k$ for at least one $i$, where $1 \leq k \leq n$. The identity counts the number of functions in $\cap_{k=1}^n A_k$ in two different ways.

First way: The set $\cap_{k=1}^n A_k$ is the set of onto functions from $\{1, 2, \ldots, n\}$ to itself. Since an onto function from a finite set to itself must be one-to-one as well, the intersection of the $A_k$'s is the set of bijections on $\{1, 2, \ldots, n\}$. There are $n$ choices for $f(1)$, followed by $n-1$ choices for $f(2)$ given $f(1)$, and so forth. Thus: $$\text{There are $n!$ functions in } \bigcap_{k=1}^n A_k.$$

Second way: Now we want to use the principle of inclusion-exclusion. The functions in the intersection of $\bar{A}_{i_1}, \bar{A}_{i_2}, \ldots, \bar{A}_{i_k}$ are those that map from $\{1, 2, \ldots, n\}$ to $\{1, 2, \ldots, n+r\} - \{i_1, i_2, \ldots i_k\}$. There are $n-k+r$ elements in this latter set, and so there are $(n-k+r)^n$ functions in $\cap_{j=1}^k \bar{A}_{i_j}$. In addition, there are $n^n$ total functions from $\{1, 2, \ldots, n\}$ to itself. By inclusion, exclusion, then, we also have the following: $$\text{There are } \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+r)^n \text{ functions in } \bigcap_{k=1}^n A_k.$$

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.