3

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?

Mick A
  • 10,208
user135483
  • 31
  • He shows how it is a special case on the next page (193). It is not supposed to be readily obvious since it takes five lines to show it. – adam W Mar 14 '14 at 18:48
  • Okay, he shows proof for the statement (your "first one") but I don't see how it is a special case either... – adam W Mar 14 '14 at 18:58

2 Answers2

1

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.

Mick A
  • 10,208
0

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)$$

adam W
  • 5,565
  • Though I am not too sure still since I do not see where $x$ went in the second formula here for $\Delta^k g(x)$. The authors may have done better to just not even mention formula 5.45 there since it does not seem to matter anyway, they just prove things without using it. – adam W Mar 14 '14 at 19:19