# Numerical differentiation with Binomial Theorem

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

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 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.

• from induction it comes easily. Also take a look here. Indeed there is no need of continuity of the last derivative at the point – Masacroso Oct 26 '18 at 18:26
• @Masacroso I fail to see how this follows easily from induction. The binomial coefficients are generated easily from an inductive definition, however the lower coefficients are attached to $f$ evaluated at two different points. – Robert Wolfe Oct 26 '18 at 18:35
• If you write out the difference quotients to higher degrees as you compute them then you’ll inevitably form a triangle. Indeed the binomial coefficients appear because the procedure is analogous to generating Pascal’s triangle. – adfriedman Oct 26 '18 at 18:39
• If this really is trivial, I welcome a formal answer. – Robert Wolfe Oct 26 '18 at 18:41
• I’ll post one in half an hour when I’m at a computer if no one else does in the meantime – adfriedman Oct 26 '18 at 18:43

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![z^m](1-e^z)^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

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

• This is just about a copy and paste of one of your answers on the questions I've linked. I was more looking for an analytic approach, but +1 for the power of algebra. – Robert Wolfe Oct 26 '18 at 19:18
• @RobertWolfe: Thanks for the credit. In fact this is a slight simplification to my former answer, since it avoids the usage of the substitution rule. But this is a minor aspect. – Markus Scheuer Oct 26 '18 at 19:21

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}

• Maybe I'm missing something. But is it obvious that $L_n^{(n)}(x_0)=f^{(n)}(x_0)$? – Robert Wolfe Oct 28 at 14:34
• @RobertWolfe Thank you for the comment, I had used it in my answer. This is the usual practice in numeric methods. – Yuri Negometyanov Oct 28 at 22:19
• Even if I take a secant line $L_1(x)=(x-x_1)/(x_0-x_1)\cdot f(x_0)+(x-x_0)/(x_1-x_0)\cdot f(x_1)$, I don't necessarily get $L_1'(x_0)=f'(x_0)$. Have you possibly switched some $x$'s and $x_0$'s? – Robert Wolfe Oct 29 at 19:59
• @RobertWolfe The Lagrange interpolation polynomial of $n$ order is required to take given values at $n+1$ given points. These points were denoted $(x_0+kh, y_k$ to avoid mixing with the variable $x.$ I've confirmed $L_n(x).$ many times. Perhaps it is mistaken. Can you tell me which of the given points showed this? – Yuri Negometyanov Oct 29 at 20:56

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.

• What you have called your first use of L'Hopital is actually equivalent to strict differentiability. A discussion of which is given here: math.stackexchange.com/questions/2945310/… As I've assumed continuity of the derivative, this doesn't form a problem. But the oversight of mention makes me cautious to accept too quickly. I'm going to review this proof some more. – Robert Wolfe Oct 31 '18 at 17:37
• Sorry, I didn't understand your comment. Can you be more specific? Is that my use of L'Hopital with nets? – André Porto Oct 31 '18 at 18:14
• What I used is that, fixing a sequence $a_{h_n}$ converging to $x$, we apply L'Hopital to the continuous limit $\lim_{h\to0,\ u\to x}(...)=L$, then so does the limit for the sequence $(h_n, a_{h_n})_{n\in\mathbb N}$. Since this is true for all sequence $(h_n, a_{h_n})_{n\in\mathbb N}$, it is true for $(h, a_h)$. – André Porto Oct 31 '18 at 18:33
• It is not in general true, that if you have sequences (or nets) $\{x_n\}$ and $\{y_n\}$ such that $x_n\rightarrow x$ and $y_n\rightarrow x$ such that $x_n\neq y_n$, that we can conclude $$\lim_{n\rightarrow\infty}\frac{f(y_n)-f(x_n)}{y_n-x_n}=f'(x).$$ This property is slightly stronger than differentiability. – Robert Wolfe Oct 31 '18 at 18:50
• Is it true for continuously differentiability? – André Porto Oct 31 '18 at 19:20

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}