3
$\begingroup$

Expression

I have somehow stumbled upon this expression (I believe I have proved it, but that is not important right now), which I have tried to simplify by writing it like something like this (I have been playing with powers of natural numbers and something similar to Pascal's triangle) :

n! = (t-1)^n , t^a=(a+1)^n

n is a natural number; and t^a is used to replace powers of t's in (t-1)^n with natural numbers to the power of n. (Not to be used as direct equalities!)

For example, take 5 for n:

5! = (t-1)^5

5! = t^5 - 5 * t^4 + 10 * t^3 - 10 * t^2 + 5 * t^1 - 1

5! = 6^5 - 5 * 5^5 + 10 * 4^5 - 10 * 3^5 + 5 * 2^5 - 1

5! = 120

120 = 120

This is true for any natural number n.

Questions


Firstly, is there a similar or exact expression or formula out there already declared and explained with all of its properties, and if yes what is, where is it, and is it useful in any way?


Mainly, are there and what are other more convenient ways to express or write this down, maybe even simplify?

UPDATE: @abiessu Thanks, for your answer to this part.

UPDATE: @abiessu and @DanielFischer♦ Thanks, for correcting my expression of notation.


And lastly, if you wish, how would you prove such an expression with most elegance?

UPDATE: @abiessu Thanks, for your answer to this part.


UPDATES:

The comments will for sure give you a better idea of what I'm look for and hoping to find.

Use $$ n!=(n+1)^n-nn^n+\binom n2(n-1)^n-\dots $$ instead to look at the expression in its better notation easier to understand I believe.

$\endgroup$
  • 1
    $\begingroup$ Please note that $(t-1)^n \neq t^n-n(t-1)^n+\binom n2(t-2)^n-\dots$... $\endgroup$ – abiessu Feb 26 '16 at 19:35
  • $\begingroup$ Okay, look at it this way: $(6-1)^5 \neq 6^5-5\cdot 5^5+10\cdot 4^5\dots$ $\endgroup$ – abiessu Feb 26 '16 at 19:48
  • 2
    $\begingroup$ You haven't explained very well what you're doing, and so you're being misunderstood. It's tempting to write things as equalities, but that makes misunderstandings more likely here. If I understood correctly, what you are doing is, given $n$, first expand $(t-1)^n$ via the binomial formula. Then, in that polynomial, you replace every power $t^a$ of $t$ with $(a+1)^n$. And the resulting number turns out - if you haven't made a mistake - to be $n!$. Is that right? $\endgroup$ – Daniel Fischer Feb 26 '16 at 19:55
  • 1
    $\begingroup$ The fact that this identity mirrors what you find in Pascal's Triangle is directly related to how you would take the $n$th finite difference of the polynomial $p(x)=x^n$. $\endgroup$ – abiessu Feb 26 '16 at 20:06
  • 2
    $\begingroup$ This is closely related to Binomial Sum: Values $\endgroup$ – robjohn Mar 13 '16 at 13:21
2
$\begingroup$

Note that $k^m$ can be written as a linear combination of $\binom{k}{j}$ for $j$ from $0$ to $m$. If fact, this is what the Stirling Numbers of the Second Kind are perfect for: $$ \newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}} k^m=\sum_{j=0}^mj!\stirtwo{m}{j}\binom{k}{j}\tag{1} $$ Using $(1)$ and other binomial identities, we get $$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(n-k+1)^n &=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{i=0}^n(-1)^i\binom{n}{i}(n+1)^{n-i}k^i\tag{2}\\ &=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{i=0}^n(-1)^i\binom{n}{i}(n+1)^{n-i}\sum_{j=0}^ij!\stirtwo{i}{j}\binom{k}{j}\tag{3}\\ &=\sum_{i=0}^n\sum_{j=0}^i(-1)^i\binom{n}{i}(n+1)^{n-i}j!\stirtwo{i}{j}\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{k}{j}\tag{4}\\ &=\sum_{i=0}^n\sum_{j=0}^i(-1)^i\binom{n}{i}(n+1)^{n-i}j!\stirtwo{i}{j}\sum_{k=0}^n(-1)^k\binom{n}{j}\binom{n-j}{k-j}\tag{5}\\ &=\sum_{i=0}^n\sum_{j=0}^i(-1)^i\binom{n}{i}(n+1)^{n-i}j!\stirtwo{i}{j}(-1)^n[j=n]\tag{6}\\ &=(-1)^n\binom{n}{n}(n+1)^{n-n}n!\stirtwo{n}{n}(-1)^n\tag{7}\\[9pt] &=n!\tag{8} \end{align} $$ Explanation:
$(2)$: apply the Binomial Theorem to $(n-k+1)^n$
$(3)$: apply $(1)$ to $k^i$
$(4)$: rearrange factors
$(5)$: $\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$
$(6)$: $\sum_{k=0}^n(-1)^k\binom{n-j}{k-j}=(1-1)^{n-j}$ which is $1$ only if $n=j$ and $0$ otherwise
$(7)$: if $j=n$, then $i=n$
$(8)$: evaluate

$\endgroup$
  • $\begingroup$ This is good, but it does not appear to cover the $1,-5,10,-10,5,-1$ pattern observed by the OP. $\endgroup$ – abiessu Mar 14 '16 at 15:10
  • $\begingroup$ @abiessu: if we plug in $n=5$, we get that $(-1)^k\binom{5}{k}=\{1,-5,10,-10,5,-1\}$ $\endgroup$ – robjohn Mar 14 '16 at 15:12
  • $\begingroup$ Oops, now I see it, thank you. :-) $\endgroup$ – abiessu Mar 14 '16 at 15:31
2
$\begingroup$

First, we skip the notation issue and make the claim

$$n!=(n+1)^n-nn^n+\binom n2(n-1)^n-\dots\pm \binom n2 3^n\pm n2^n\pm 1\tag 1$$

To prove this, take the $n$th (forward) finite difference of the polynomial $p(x)=x^n$:

$$\Delta(p(x))=p(x+1)-p(x)\\ =(x+1)^n-x^n\\ \Delta^2(p(x))=p(x+2)-2p(x+1)+p(x)\\ \Delta^3(p(x))=p(x+3)-3p(x+2)+3p(x+1)-p(x)\\ \vdots\\ \Delta^n(p(x))=p(x+n)-np(x+n-1)+\binom n2p(x+n-2)-\dots\pm\binom n2p(x+2)\pm np(x+1)\pm 1\\ \Delta^n(p(1))=(n+1)^n-nn^n+\binom n2(n-1)^n-\dots\pm \binom n2 3^n\pm n2^n\pm 1$$

Note that the $n$th finite difference of any degree-$n$ polynomial is a constant. This constant happens to be equivalent to the coefficient of the highest-degree term when it is written in binomial form. In particular, if we write another polynomial $q(x)=\binom xn={x(x-1)(x-2)\dots(x-n+1)\over n!}$ we see that the highest-degree term of $q(x)$ has coefficient $1\over n!$ when written in standard form. Because of the Binomial Coefficient identity

$$\binom {x+1}n-\binom xn = \binom x{n-1}$$

we have that the $n$th finite difference of $q(x)$ is the constant value $\Delta^n(q(x)) = 1$. So this tells us that the value of our $n$th finite difference of $p(x)$ must be

$$\Delta^n(p(x))=n!$$

This proves the identity in $(1)$. For comparison, consider the inductive proof of a similar identity in my answer here: https://math.stackexchange.com/a/1115939/86846.

$\endgroup$
  • $\begingroup$ Thank you for your valuable input to my question, but I'm still wondering and interested in about who else made this claim before and pointed out some more information about its properties and uses in general or specifics. $\endgroup$ – Vepir Feb 26 '16 at 21:00
  • 2
    $\begingroup$ The general idea of finite differences goes back at least as far as Newton, and probably goes further back to the time when polynomials were first considered. This particular claim might be attributed to Vandermonde (see trans4mind.com/personal_development/mathematics/series/…), but may have come about earlier than that. $\endgroup$ – abiessu Feb 26 '16 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.