Please help me prove this equation in page 190 of Concrete Mathematics 2nd Ed. book by D. Knuth:
$f(k) = {r - sk \choose n} = {1 \over n!}(-1)^n s^n k^n + ... = (-1)^n s^n {k \choose n} + ... $
I believe this is the Newton series of $f(k)$ since that is the topic being explained on the page. But I can't prove it.
\begin{eqnarray*} \binom{r-sk}{n} &=& \dfrac{(r-sk)!}{n!(r-sk-n)!} \\ &=& \dfrac{1}{n!}(r-sk)(r-sk-1) \cdots (r-sk-n+1) \\ &=& \dfrac{1}{n!}\left[(-sk)^n + \alpha_{n-1}(-sk)^{n-1} + \cdots + \alpha_{1}(-sk)^1 + \alpha_{0} \right] \\ &&\qquad\text{where $\alpha_i,\; i=0,1,\ldots,n-1$, are (constant) coefficients involving $r$} \\ &=& \dfrac{1}{n!} (-1)^ns^nk^n + \cdots \end{eqnarray*}
Note that the only important term here is the leading term. We don't care what the coefficients, $\alpha_i,$ are for the other terms because they will not be used when we come to apply identity (5.42). This is why the book doesn't show them and doesn't discuss their value.
For the next equality, again we really only care about the leading term.
\begin{eqnarray*} \binom{k}{n} &=& \dfrac{1}{n!} \dfrac{k!}{(n-k)!} \\ &=& \dfrac{1}{n!} k(k-1) \cdots (k-n+1) \\ &=& \dfrac{1}{n!} \left[k^n + \beta_{n-1}k^{n-1} + \cdots + \beta_1 k^1 \right] \\ &&\qquad\text{where $\beta_i,\; i=1,\ldots,n-1$, are (constant) coefficients} \\ &=& \dfrac{1}{n!} k^n + \cdots \end{eqnarray*}
So we can write our leading term $\quad\dfrac{1}{n!} (-1)^ns^nk^n\quad$ as $\quad(-1)^ns^n \binom{k}{n}$.
Making this change alters the coefficients of the remaining terms but, again, we don't care about their value anyway.
