Is there a proof of $\sum_{n=0}^x {{(-1)^n(x-n+1)^x}\over{n!(x-n)!}} = 1$ using induction?

Question

Can someone prove (or disprove) this equality? $$\sum_{n=0}^x {{(-1)^n(x-n+1)^x}\over{n!(x-n)!}} = 1$$ where the value of $x$ can vary. This is a pattern found in derivatives and stuff but I'm not sure how to prove it because of that $x$ to the $x$ power thing... I have tried logs... help?

Answer 1

Note that the denominator looks like the denominator of $\binom{x}n$; that suggests multiplying both sides by $x!$ and trying to show that

$$\sum_{n=0}^x(-1)^n\binom{x}n(x-n+1)^x=x!\;.$$

The alternating sign in the sum strongly suggests an inclusion-exclusion argument. It might help to write out a few terms:

$$\binom{x}0(x+1)^x-\binom{x}1x^x+\binom{x}2(x-1)^x-\ldots+(-1)^x\binom{x}x1^x\;.$$

The $x!$ on the righthand side suggests that we should think about counting permutations of $[x]=\{1,\ldots,x\}$, but the $(x+1)^x$ in the first term on the left seems to count $x$-tuple chosen from a set of $x+1$ elements, say $S_x=\{0,1,\ldots,x\}$. How could you get permutations of $[x]$ by choosing $x$-tuples from $S_x$?

You could pick an $x$-tuple from $S_x$ and throw it away if it didn’t contain $1$, or if it didn’t contain $2$, or in fact if it failed to contain any specific element of $[x]$. There are

$$(x+1)^x=\binom{x}0(x+1)^x$$

$x$-tuples that can be formed from $S_x$, for each $n\in[x]$ there are $x^x$ that don’t contain $n$, and there are $\binom{x}1$ elements of $[x]$, so getting rid of these ‘bad’ $x$-tuples leaves us, at a first approximation, with

$$\binom{x}0(x+1)^x-\binom{x}1x^x\;.$$

At this point the nature of the inclusion-exclusion argument should be pretty clear.