Starting with a sequence .
Continuing to do the difference the way you showed gives the same result as:
Why? Draw a graph corresponding to the subtraction. Something like (for your 3rd power case):
[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.
You are starting with the sequence:
So the answer after doing the differencing is:
This is the same as by a simple counting argument with inclusion-exclusion.
Consider the set of all words of length over an alphabet of characters, call this .
counts the number of words in with no repeating characters.
counts all words in , then subtracts all words that only use at most characters (which requires inclusion exclusion).
These two statements count the same thing.