Concrete Mathematics, Newton Series and Inversion

Question

In section 5.3 of Concrete Mathematics, on the bottom of page 192, "A special case of the rule (5.45) we've just derived for Newton's series can be rewritten in the following way:" (this is 5.48)

$g(n) = \displaystyle\sum\limits_{k}^{} \binom{n}{k}(-1)^kf(k) \iff f(n) = \displaystyle\sum\limits_{k}^{} \binom{n}{k}(-1)^kg(k)$

5.45 is:

$g(a+x) = \displaystyle\frac{g(a)}{0!}x^\underline 0 + \displaystyle\frac{\Delta g(a)}{1!}x^\underline 1 + \displaystyle\frac{\Delta^2 g(a)}{2!}x^\underline 2 +\ldots$

I can understand each part individually but I cannot understand why the first one is a special case of the second one. Can someone explain the connection to me?

Answer 1

The second equation (5.45 not 5.48--a typo in your question) in only slightly different form is $$ g(a+x) = \sum_{k\ge 0} \binom{x}{k}\Delta^k g(k)$$ If we have $a=0$, $n=x$ and for some $f$ $$ \Delta^k g(x) = (-1)^k f(k)$$ (which I believe is the special case the authors means) then we have that $$g(n) = \sum_{k\ge 0} \binom{n}{k}(-1)^k f(k)$$

Answer 2

5.48 is a special case inasmuch as: if functions $f$ and $g$ satisfy property 5.48 then equation 5.45 (by way of its equivalent 5.44) is also satisfied. Equation 5.44 is:

$$f(x) = f(0)\binom{x}{0} + \Delta f(0)\binom{x}{1} + \Delta^2 f(0)\binom{x}{2} + \Delta^3 f(0)\binom{x}{3} + \ldots\;\;.$$

To see this, from 5.48, we have,

\begin{eqnarray*} f(n) &=& \sum_k{\binom{n}{k}(-1)^kg(k)} \\ \therefore \Delta f(n) &=& \sum_k{\binom{n}{k-1}(-1)^kg(k)} \qquad\text{using $\Delta \left(\binom{x}{k}\right) = \binom{x}{k-1}$ from pg. 189} \\ \text{and generally} \\ \Delta^r f(n) &=& \sum_k{\binom{n}{k-r}(-1)^kg(k)} \\ \therefore \Delta^r f(0) &=& (-1)^rg(r) \\ && \text{since all the binomial coefficients in the sum are $0$ except for when $k=r$} \\ && \text{when we have $\binom{0}{0}=1.$} \end{eqnarray*}

Now we take RHS (5.44) and try to show it equals LHS (5.44), using $n$ instead of $x$.

\begin{eqnarray*} RHS(5.44) &=& \sum_{k\geq 0}{\Delta^k f(0)\binom{n}{k}} \\ &=& \sum_{k\geq 0}{(-1)^kg(k)\binom{n}{k}} \qquad\text{from above.} \end{eqnarray*}

The rest, to show this equals $f(n)$, is shown in the text on pg. 193.