# Thread: Number sequences and exponents

1. ## Number sequences and exponents

I'm pretty new to this site, so if this is in the wrong section (I think it is), please tell me what to do!

First off, I need a better way to word all this...but mostly I'm just looking for an explanation to this:
The difference between integers to the 1st power is 1.
$1^1-0^1=1$

The difference between the difference between integers to the 2nd power is 2.
$2^2-1^2=3$
$1^2-0^2=1$

$3-1=2$

The difference between the difference between the difference between integers to the 3rd power is 6.
$3^3-2^3=19$
$2^3-1^3=7$
$1^3-0^3=1$

$19-7=12$
$7-1=6$

$12-6=6$

And, the difference between the difference between the difference between the difference between 4th power is 24.
$4^4-3^4=175$
$3^4-2^4=65$
$2^4-1^4=15$
$1^4-0^4=1$

$175-65=110$
$65-15=50$
$15-1=14$

$110-50=60$
$50-14=36$

$60-36=24$

If the exponent for the example above is $n$, then $n!$ is the result (from what I can tell). Why?

2. Starting with a sequence $a_0, a_1, ..., a_n$.
Continuing to do the difference the way you showed gives the same result as:
$\sum_{k=0}^n \binom{n}{k}(-1)^ka_k$

Why? Draw a graph corresponding to the subtraction. Something like (for your 3rd power case):
19
\
12
/ \
7 6
\ /
6
/
1

[doesn't really look nice since spaces are removed]

The number of times an initial number in the sequence is added or subtracted is the number of paths from that number to the answer. It is positive or negative depending on (even/odd) parity of how many up edges are taken.

Now:
You are starting with the sequence: $n^n, (n-1)^n, ..., 1^n, 0^n$
So the answer after doing the differencing is:
$\sum_{k=0}^n \binom{n}{k}(-1)^k(n-k)^n$

This is the same as $n!$ by a simple counting argument with inclusion-exclusion.

Consider the set of all words of length $n$ over an alphabet of $n$ characters, call this $W$.

$n!$ counts the number of words in $W$ with no repeating characters.

$\sum_{k=0}^n \binom{n}{k}(-1)^k(n-k)^n$ counts all words in $W$, then subtracts all words that only use at most $n-1$ characters (which requires inclusion exclusion).

These two statements count the same thing.

3. Similar to snowtea, its a start

$\displaystyle \sum_{i=1}^n (-1)^{2i+1}\times (i^i-(i-1)^i) = n!$

4. Originally Posted by snowtea
Why? Draw a graph corresponding to the subtraction. Something like (for your 3rd power case):
19
\
12
/ \
7 6
\ /
6
/
1

[doesn't really look nice since spaces are removed]
My ascii diagram in the above post would look better in a code block (unfortunately it is too late to edit):

Code:
19
\
12
/  \
7    6
\  /
6
/
1