For all real numbers $x$, and all non-negative integers $n$,
$$
x^n = \sum_{k=0}^{n} S(n,k)\frac{x!}{(x-k)!}
$$
I have a 2 questions with the proof that my textbook presents.
First they say that they will prove this for a stronger statement — that the equality holds for all positive integers $x$. (1) Why is this a stronger statement? Aren't stronger statements usually more generalized?
The LHS is the number of all functions from $1,\ldots,n$ to $1,\ldots,x.$ (2) Why is this "obvious"? (What does it mean?).
Best Answer
I don’t know exactly what your text actually says, but the general fact is that
$$x^n=\sum_{k\ge 0}\left\{n\atop k\right\}x^{\underline k}\;,\tag{1}$$
where $x^{\underline k}=x(x-1)(x-2)\dots(x-k+1)$; this holds for integer $n\ge 0$. Note that if $x$ is an integer and $x\ge k$, then $$x^{\underline k}=\frac{x!}{(x-k)!}\;,$$ and $(1)$ becomes your formula.
As for the second question, if $n$ and $x$ are positive integers, choosing a function $f$ from $\{1,\dots,n\}$ to $\{1,\dots,x\}$ is the same as choosing a value in $\{1,\dots,x\}$ for each $k\in\{1,\dots,n\}$. There are $x$ different ways to choose $f(1)$. For each of those there are $x$ ways to choose $f(2)$, so there are altogether $x^2$ combinations of values of $f(1)$ and $f(2)$. Each new choice of an $f(k)$ can be made in $x$ different ways, so in the end you have $x^n$ possible sequences of choices, i.e., $x^n$ functions from from $\{1,\dots,n\}$ to $\{1,\dots,x\}$.