Numerical differentiation with Binomial Theorem

Question

In George Shilov's Elementary Real and Complex Analysis, there is a problem which asks us prove

If $f$ is twice differentiable on some open interval and the second derivative is continuous at $x$, then prove that $$f''(x)=\lim_{h\rightarrow 0}\frac{f(x)-2f(x+h)+f(x+2h)}{h^2}\,.$$

This is a common fact in numerical differentiation to approximate derivatives at the left-hand point and is fairly immediate from two applications of Taylor's Theorem with Lagrange Remainder. However, this was not the end of Shilov's problem. He also states

Find a similar expression for $f^{(n)}(x)$ (with appropriate hypotheses).

In the back of his book, he asserts that

$$f^{(n)}(x)=\lim_{h\rightarrow 0}\frac{1}{h^n}\sum_{k=0}^n (-1)^k\binom{n}{k}f(x+kh)$$

which I found interesting enough to at least remember, if not attempt. However, I recently came upon an application where this formula would be useful and attempted to prove it. However, it seems there was an error in Shilov's claim. He must have meant

$$(-1)^nf^{(n)}(x)=\lim_{h\rightarrow 0}\frac{1}{h^n}\sum_{k=0}^n (-1)^k\binom{n}{k}f(x+kh)$$

because working out $n=3$ and applying Lagrange's Remainder three times results in

$$\frac{f(x)-3f(x+h)+3f(x+2h)-f(x+3h)}{h^3}=\frac{1}{3!}\left(-3f'''(\xi_1)+24f'''(\xi_2)-27f'''(x_3)\right)$$

which gives the corrected limit (with continuity of $f^{(3)}$ at $x$ assumed).

Is there an easy way to go about proving this result in general?

We can attack this fairly directly, without induction. But this becomes equivalent to proving several interesting binomial identities:

$$\sum_{k=0}^n(-1)^k\binom{n}{k} k^m=\begin{cases} (-1)^n n!&\text{ if }m=n\\0&\text{ if }0\leq m<n\end{cases}$$

The first of which was tackled here while the others seem to have gone largely unasked. The case $m=1$ is tackled here and here, and I can see that I could continue the approaches taken in these answers by differentiating several times. The book-keeping isn't too awful because all these identities are just sums of $0$s. Thus $0\leq m<n$ isn't too bad, if we can do $m=1$. However, proving the cases $m=1$ and $m=n$ aren't entirely trivial.

Shilov seems to have hidden an interesting exercise in a terse sentence without any hint that it would be interesting. This makes me wonder if there's an easier way to go about proving this result.

Answer 1

Here we show the validity of the binomial identity.

We obtain for integral $0\leq m \leq n$: \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{(-1)^k\binom{n}{k}k^m}\\ &=\sum_{k=0}^n\binom{n}{k}(-1)^km![z^m]e^{kz}\tag{1}\\ &=m![z^m]\sum_{k=0}^n\binom{n}{k}\left(-e^{z}\right)^k\tag{2}\\ &=m^n\tag{3}\\ &=m![z^m]\left(1-\left(1+z+\frac{z^2}{2}\cdots\right)\right)^n\tag{4}\\ &=(-1)^nm![z^m]\left(z+\frac{z^2}{2}+\cdots\right)^n\tag{5}\\ &\color{blue}{=} \begin{cases} \color{blue}{(-1)^nn!}&\qquad\color{blue}{m=n}\\ \color{blue}{0}&\qquad\color{blue}{0\leq m<n} \end{cases} \end{align*}

Comment:

• In (1) we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series and we note that $$k^m=m![z^m]e^{kz}=m![z^m]\sum_{j=0}^\infty\frac{(kz)^{j}}{j!}$$

• In (2) we do some rearrangements as preparation for the next step.

• In (3) we apply the binomial theorem.

• In (4) we expand the exponential series to better see what's going on.

• In (5) we simplify the expression and observe that the series starts with powers in $z$ which are greater or equal to $n$.

Answer 2

Traditionally used numerical approaches start from the minimally possible polynomial model.

Estimation of the errors uses the next order polynomial in accordance with the Taylor series.

Let us build Lagrange interpolation polynomial in the form of

\begin{align} &L_n(x) = \dfrac{(x-x_1)(x-x_2)\dots(x-x_n)}{(x_0-x_1)(x_0-x_2)\dots(x_0-x_n)} f(x_0)\\[4pt] &+ \dfrac{(x-x_0)(x-x_2)(x-x_3)\dots(x-x_n)}{(x_1-x_0)(x_1-x_2)(x_1-x_3)\dots(x_1-x_n)} f(x_1)+\dots\\[4pt] &+ \dfrac{(x-x_0)(x-x_1)\dots(x-x_{k-1})(x-x_{k+1})(x-x_{k+2})\dots(x-x_n)} {(x_k-x_0)(x_k-x_1)\dots(x_k-x_{k-1})(x_k-x_{k+1})(x_k-x_{k+2})\dots(x_k-x_n)} f(x_k)\\[4pt] &+\dots + \dfrac{(x-x_0)(x-x_1)\dots(x-x_{n-2})(x-x_n)} {(x_{n-1}-x_0)(x_{n-1}-x_1)\dots(x_{n-1}-x_{n-2})(x_{n-1}-x_n)} f(x_{n-1})+\dots\\[4pt] &+ \dfrac{(x-x_0)(x-x_1)\dots(x-x_{n-1})} {(x_n-x_0)(x_n-x_1)\dots(x_n-x_{n-1})} f(x_n). \end{align}

If $\quad x_k=x_0+kh,$ then

\begin{align} &L_n(x) = \dfrac{(x-x_1)(x-x_2)\dots(x-x_n)}{(-h)(-2h)\dots(-nh)} f(x_0)\\[4pt] &+ \dfrac{(x-x_0)(x-x_2)(x-x_3)\dots(x-x_n)}{(h)(-h)(-2h)\dots(-(n-1)h)} f(x_0+h)+\dots\\[4pt] &+ \dfrac{(x-x_0)(x-x_1)\dots(x-x_{k-1})(x-x_{k+1})(x-x_{k+2})\dots(x-x_n)} {(kh)((k-1)h)\dots(h)(-h)(-2h)\dots(-(n-k)h)} f(x_0+kh)+\dots\\[4pt] &+ \dfrac{(x-x_0)(x-x_1)\dots(x-x_{n-2})(x-x_n)} {((n-1)h)((n-2)h)\dots(h)(-h)} f(x_0+(n-1)h)+\dots\\[4pt] &+ \dfrac{(x-x_0)(x-x_1)\dots(x-x_{n-1})} {(nh)((n-1)h)\dots(h)} f(x_0+nh),\\[8pt] \end{align}

\begin{align} &L_n^{(n)}(x) = \dfrac1{h^n}\Big(f(x_0+nh) - nf(x_0+(n-1)h)+\dots +(-1)^{n-k}\dbinom nkf(x_0+kh)\\[4pt] &+\dots +(-1)^{n-1}nf(x+h)+(-1)^nf(x_0)\Big) \end{align}

Answer 3

I will exhibit a proof by induction here. Actually I will prove a slightly more general result, constructing, for $f$, a family of functions $F_k(x,h)$ satisfying that, for any net $(a_h)$ such that $\displaystyle\lim_{h\to0} a_h=x$,

$$ \displaystyle\lim_{h\to0} \frac{F_k(a_h,h)}{h^k} = f^{(k)}(x). $$

The net $(a_h)$ such that $\displaystyle\lim_{h\to0} a_h=x$ is necessary for the induction step. To obtain the result we want, just pick $a_h=x$ for all $h$.

The family $F_k(x,h)$ is defined by $F_1(x,h)= f(x+h)-f(x)$ and $F_k(x,h) = F_{k-1}(x+h,h) - F_{k-1}(x,h)$, which we will see that are given by the formula

$$ F_k(x,h) = \sum_{j=0}^{k} (-1)^{k-j}{{n}\choose{j}}f(x+jh). $$

So what you said is accurate. There is a mistake at the formula given by the book.

Let us first prove the result for $F_1(x,h) = f(x+h)-f(x)$. If we have $\displaystyle\lim_{h\to0}a_h=x$, then, using L'Hospital, we easily verify that

$$ \lim_{h\to0} \frac{F_1(a_h,h)}{h}=\lim_{h\to0} \frac{f(a_h+h)-f(a_h)}{h}=\lim_{h\to0} f'(a_h+h)=f'(x). $$

Define the auxiliary function $\widehat{F_1} = f'(x+h)-f'(x)$. We easily verify that

$$ \frac{\partial F_1}{\partial x}=\widehat{F_1}. $$

And substituing $f$ by $f'$ since the begining, we get that for any $\displaystyle\lim_{h\to0}a_h=x$,

$$ \lim_{h\to0} \frac{\widehat{F_1}(a_h,h)}{h}=f''(x). $$

Consider $F_2(x,h)=F_1(x+h,h)-F_1(x,h)$. Suppose that $\displaystyle\lim_{h\to0}a_h=x$ and let us evaluate $$ \displaystyle\lim_{h\to0} \frac{F_2(a_h,h)}{h^2} = \displaystyle\lim_{h\to0} \frac{F_1(a_h+h,h)-F_1(a_h,h)}{h^2}. $$ For each $h$, using the mean value theorem on the first variable, there exists $c_h$ in the interval between $a_h$ and $a_h+h$ (so certainly $|c_h-a_h|\leq |h|$) such that $$ F_1(a_h+h,h)-F_1(a_h,h) = \frac{\partial F_1}{\partial x}(c_h,h)h=\widehat{F_1}(c_h,h)h. $$ Then, certainly $\displaystyle\lim_{h\to0}c_h=x$ and we have that

$$ \displaystyle\lim_{h\to0} \frac{F_2(a_h,h)}{h^2} = \displaystyle\lim_{h\to0} \frac{\widehat{F_1}(c_h,h)}{h}=f''(x). $$

Define the auxiliary function $\widehat{F_2}=\widehat{F_1}(x+h,h)-\widehat{F_1}(x,h)$. It is easy to check that

$$ \frac{\partial F_2}{\partial x}=\widehat{F_2}. $$

And, substituing $f$ by $f'$ since the begining, we get that

$$ \lim_{h\to0} \frac{\widehat{F_2}(a_h,h)}{h^2}=f^{(3)}(x). $$

We may proceed by induction, defining for each $k\in\mathbb N$, $F_k(x,h)=F_{k-1}(x+h,h)-F_{k-1}(x,h)$, in an argument similar to what we did for $F_2$, if $\lim_{h\to0} a_h=x$, we obtain $\lim_{h\to0} c_h=x$ such that

$$ \displaystyle\lim_{h\to0} \frac{F_k(a_h,h)}{h^k} = \displaystyle\lim_{h\to0} \frac{\widehat{F_{k-1}}(c_h,h)}{h^{k-1}}=f^{(k)}(x). $$

Then define the auxiliary function $\widehat{F_k}=\widehat{F_{k-1}}(x+h,h)-\widehat{F_{k-1}}(x,h)$ and check that

$$ \frac{\partial F_k}{\partial x}=\widehat{F_k}. $$

And, substituing $f$ by $f'$ since the begining, we get that

$$ \lim_{h\to0} \frac{\widehat{F_k}(a_h,h)}{h^k}=f^{(k+1)}(x). $$

Finally, it is easy to verify that $F_2(x,h)= F_1(x+h,h)-F_1(x,h) = f(x+2h)-2f(x+h)+f(x)$. Then $$F_3(x,h) = F_2(x+h,h)-F_2(x,h)= f(x+3h) - 3f(x+2h) + 3f(x+h) - f(x).$$

We derive the formula: $$ F_k(x,h) = \sum_{j=0}^{k} (-1)^{k-j}{{n}\choose{j}}f(x+jh), $$ which we will not be entering in more details, but can be easily proved by induction.

Answer 4

I'm not sure I'm contributing anything, maybe I misunderstood since this feels like essentially a duplicate of this link. $\newcommand{\fd}{\Delta}$ Its not so hard (via e.g. repeated applications of l'Hopital, as Paramanand shows in that link) to show that you are actually interested in iterated forward finite differences $$ \fd_h^1 f(x) := f(x+h)-f(x), \quad \fd_h^{n+1} f(x) := \fd_h^1[\fd_h ^nf] (x)=\fd_h ^nf(x+h) - \fd_h ^nf(x)$$ And your hope is that $$ \fd_h ^nf (x) = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}k f(x+kh)$$ By rescaling $f$, and choosing a different $x$, it would suffice to do this for $h=1$; let $\fd:=\fd^1_1$ for easy typing. Now the inductive proof for this is straightforward using the Pascal triangle,

\begin{align} \fd^{n+1}f(x)&=\Delta\left[\sum_{k=0}^{n} (-1)^{n-k} \binom{n}k f(\bullet +k)\right](x) \\ &= \sum_{k=0}^{n} (-1)^{n-k} \binom{n}k f(x +k+1) - \sum_{k=0}^{n} (-1)^{n-k} \binom{n}k f(x+k)\\ &= \sum_{k=1}^{n+1} (-1)^{n+1-k} \binom{n}{k-1} f(x +k) + \sum_{k=0}^{n} (-1)^{n+1-k} \binom{n}k f(x+k)\\ &=(-1)^{n+1} f(x) + f(x+n+1) + \sum_{k=1}^n (-1)^{n+1-k} \underbrace{\left(\binom{n}{k-1} +\binom{n}{k}\right)}_{=\binom{n+1}{k}}f(x +k)\\ &=\sum_{k=0}^{n+1} (-1)^{n+1-k} \binom{n+1}{k}f(x +k) \end{align}