2
$\begingroup$

I was recently shown the following observation: if we have the set $$[1^2,2^2,3^2] = [1,4,9]$$ and we form a new set with two elements by subtracting each element from the element to its right, that is to say we form the new set: $$[2^2-1^2, 3^2-2^2] = [3,5]$$ and then we repeat this process, we get $$[5-3] = [2] = [2!]$$ More generally, it was seen that for any real starting number "a" followed in the original set by a+1, a+2, this would hold. That is to say: starting with the set: $$[a^2,(a+1)^2,(a+2)^2]$$ and performing the process described one always arrives at the one-element set $$[2!]$$ after 2 repitions of the subtraction process described above.

Further generalizing, this holds for any power, not just 2. Stated generally the above observed rule is then starting with the initial set $$[a^n,(a+1)^n,(a+2)^n, (a+3)^n,...,(a+(n-1))^n,(a+n)^n ]$$ and performing the subtraction process described above n times yields the single-element set $$[n!]$$ Immediately evident was that if I used this process n times on a set with n+1 elements, let's say: $$[a_0,a_1,a_2,a_3,...,a_{n-2},a_{n-1},a_n]$$ the following would result: $$\sum_{k=0}^{n} \binom nk a_{n-k}(-1)^k$$ However, this result did not make the n factorial result clear. Going on, I used the easily demonstrated fact that $$(x+1)^n-x^n = \sum_{k=1}^n \binom nkx^{n-k}$$ to find an alternative expression which consisted of a series of nested sums. First I will prove that the above expression is indeed correct.

By the binomial theorem, we have that $$(x+1)^n = \sum_{k=0}^n \binom nk x^{n-k} = \binom n0x^n+\sum_{k=1}^n \binom nk x^{n-k} = x^n+\sum_{k=1}^n \binom nk x^{n-k}$$ thus, subtracting $$x^n$$ we get $$(x+1)^n-x^n = \sum_{k=1}^n \binom nkx^{n-k}$$ Since all of the elements in our set differ by 1, this result is particularly useful. Starting again with the set $$[a^n,(a+1)^n,(a+2)^n, (a+3)^n,...,(a+(n-1))^n,(a+n)^n ]$$ we then find that subtracting two consecutive terms, means subtracting $$ (a+c)^n$$ from $$ ((a+c)+1)^n$$ where c is a positive integer that runs from 0 to n-1. From the earlier demonstrated equality, we have that $$((a+c)+1)^n-(a+c)^n = \sum_{k=1}^n\binom nk(a+c)^{n-k}$$ Thus performing the process once yields the new set: $$[\sum_{k=1}^n\binom nk(a+0)^{n-k},\sum_{k=1}^n\binom nk(a+1)^{n-k},\sum_{k=1}^n\binom nk(a+2)^{n-k},\sum_{k=1}^n\binom nk(a+3)^{n-k},...,\sum_{k=1}^n\binom nk(a+(n-2))^{n-k},\sum_{k=1}^n\binom nk(a+(n-1))^{n-k}]$$ Performing the operation again, we can ignore the outer summation and the binomial coefficients since they are the same for all the terms, and we are then faced with the problem as the original, but with c now running from 0 to (n-2). Thus with the subtraction performed twice, we have produced the set $$[ \sum_{k=1}^n(\binom nk \sum_{j=1}^{n-k}\binom {n-k}j(a)^{n-k-j}), \sum_{k=1}^n(\binom nk \sum_{j=1}^{n-k}\binom {n-k}j(a+1)^{n-k-j}), \sum_{k=1}^n(\binom nk \sum_{j=1}^{n-k}\binom {n-k}j(a+2)^{n-k-j}),..., \sum_{k=1}^n(\binom nk \sum_{j=1}^{n-k}\binom {n-k}j(a+(n-3))^{n-k-j}) \sum_{k=1}^n(\binom nk \sum_{j=1}^{n-k}\binom {n-k}j(a+(n-2))^{n-k-j}) ]$$ Clearly by repeating this process "b" times, we increase the number of nested summations to b, while decreasing the number of terms by b. We will have to introduce b "dummy iterators" (like k and j) which iterate over the sums. The most internal sum will have the sum of these variables up to the bth one. Clearly c always starts at 0 and ranges from 0 to n-b (Verify this in the above 2 iterations of the process).

In mathematical terms, if I introduce a list of dummy variables which I will call $$d_i$$ Then by repeating the subtraction process b times I produce the new set in which each term is of the form $$\sum_{d_1=1}^n\binom n{d_1} \sum_{d_2=1}^{n-d_1}\binom {n-d_1}{d_2} \sum_{d_3=1}^{n-d_1-d_2}\binom {n-d_1-d_2}{d_3}...\sum_{d_b=1}^{n-{\sum_{i=1}^{b-1}{d_i}}}\binom {n-{\sum_{i=1}^{b-1}{d_i}}}{d_{b}}(a+c)^{n-{\sum_{i=1}^{b}{d_i}}}$$ where c runs from 0 to n-b to give us the elements of the set from left to right. Since the subtraction process decreases the number of terms in the set by 1 each iteration, and we started with n+1 terms in the set, to get our single term resulting series, we should decrease the number of elements by 1 n times, that is to say, perform our subtraction process n times. That means with have now have an expression for our one-element set in terms of the nested summations, by letting $$b=n$$By our ealier formula it is also evident that c now ranges from 0 to n-n, so we can say that $$c=0$$ and eleminate it from the formula entirely. Plugging in n to our earlier formula with b, we get the one element set: $$\sum_{d_1=1}^n\binom n{d_1} \sum_{d_2=1}^{n-d_1}\binom {n-d_1}{d_2} \sum_{d_3=1}^{n-d_1-d_2}\binom {n-d_1-d_2}{d_3}...\sum_{d_n=1}^{n-{\sum_{i=1}^{n-1}{d_i}}}\binom {n-{\sum_{i=1}^{n-1}{d_i}}}{d_n}a^{n-{\sum_{i=1}^n{d_i}}}$$ Notice that when each of these dummy iterators is at their starting value, 1 $$\sum_{i=1}^n{d_i} = n $$ and $$\sum_{i=1}^{n-1}{d_i} = n-1 $$This means that with all d's at a value of 1, the final imbedded summation is $$\binom {n-(n-1)}1a^{n-n}= 1a^0=1$$ What happens if you want to increase one of the d's though? Take for example, $$d_1=2$$Now$$\sum_{i=1}^n{d_i} = n+1 $$ and $$\sum_{i=1}^{n-1}{d_i} = n $$ Therefore the value of the final imbedded term is $$\binom {n-n}1a^{n-n}= \binom 0 1a^{-1}=0$$ Clearly, if we increase any of the d's, we get a binomial coefficient that is "a number less than 1 choose 1", which is get 0. Therefore, the only non-zero term in the entire embedded summation exists when all d's are equal to 1, so the summations evaporate leaving only a product of binomial coefficients of the form: $$\binom n{d_1} \binom {n-d_1}{d_2} \binom {n-(d_1+d_2)}{d_3}...\binom {n-{\sum_{i=1}^{n-1}{d_i}}}{d_n}a^{n-{\sum_{i=1}^n{d_i}}}$$ which, by the definition of the binomial coefficients, is equal to: $$\frac {n!}{(n-d_1)!{d_1}!} \frac {(n-d_1)!}{(n-(d_1+d_2))!{d_2}!}\frac {(n-(d_1+d_2))!}{(n-(d_1+d_2+d_3))!{d_3}!}...\frac {(n-\sum_{i=1}^{n-1}{d_i})!}{(n-\sum_{i=1}^{n}{d_i})!{d_n}!}$$Since all d's are now 1, the d!'s on in the denominator are all 1 and can be removed from the expression. Additionally, and quite conveniently, all of the factorials cancel except for $$n!$$ in the numerator and $$(n-\sum_{i=1}^{n}{d_i})!$$ in the the denominator. Recall that since all d's are equal to 1, $$\sum_{i=1}^{n}{d_i} = n$$ so we can simply our final expression to $$ \frac {n!}{(n-n)!} = \frac {n!}{0!} = \frac {n!}1 = n!$$ I would like feedback on whether or not this is a valid demonstration of this fascinating observation...please let me know what you think! Also if there is a name for this phenomenon or this subtraction process I would appreciate knowing that too. I am aware that this is strongly linked to the stirling numbers of the second kind, for which reason I have tagged this post with the tag "stirling numbers".

$\endgroup$
3
  • $\begingroup$ This is called the calculus of finite differences $\endgroup$
    – Henry
    May 3 '17 at 15:35
  • $\begingroup$ A phrase to look for is "difference equations". When the starting sequence is a polynomial one, eventually one gets all zeros and just before that a constant sequence. $\endgroup$
    – coffeemath
    May 3 '17 at 15:37
  • $\begingroup$ This post answers the question too. $\endgroup$
    – EditPiAf
    Sep 18 '17 at 16:41
1
$\begingroup$

I think your method does work, although as you noticed, the derivation is quite complicated when trying to compute it directly.

This result is due to Euler, in § 25–26 of this paper. Euler proves it by induction as follows:

The basis case is obvious (and calculated explicitly in § 25, along with a few more cases to show the pattern. So suppose now that $$ a^n - n(a-1)^n + \frac{n(n-1)}{2!} (a-2)^n + \&c. = n! \tag{I} $$ (modernising Euler's notation slightly) Then this is independent of $a$, so equally $$ (a-1)^n -n(a-2)^n + \frac{n(n-1)}{2!} (a-3)^n + \&c. = n! \tag{II} $$ Subtracting II from I, $$ a^n - (n+1)(a-1)^n + \frac{(n+1)n}{2!}(a-2)^n + \&c. = 0 \tag{III} $$ (essentially what has happened here is Pascal's rule $$ \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k} $$ ), and then multiplying by $a$, $$ a^{n+1} - (n+1)a(a-1)^n + \frac{(n+1)n}{2!}a(a-2)^n + \&c. = 0 \tag{IV}. $$ Multiplying II by $n+1$ gives $$ (n+1)(a-1)^n -\frac{(n+1)n}{2!}2(a-2)^n + \frac{(n+1)n(n-1)}{3!}3 (a-3)^n + \&c. = (n+1)n! \tag{V} $$ (essentially using $ (n+1)\binom{n}{k} = (k+1)\binom{n+1}{k+1} $). Adding IV and V, $$ a^{n+1} - (n+1)(a-1)(a-1)^n + \frac{(n+1)n}{2!}(a-2)(a-2)^n + \&c. = (n+1)!, $$ so $$ a^{n+1} - (n+1)(a-1)^{n+1} + \frac{(n+1)n}{2!}(a-2)^{n+1} + \&c. = (n+1)!, $$ and hence the result is true for all positive integers $n$ by induction. To a certain extent, Euler's proof is easier to follow than it would be in modern notation where one would be mucking about with summation indices.

$\endgroup$

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.