# Convergence of finite differences to zero and polynomials

Assume that $f:\mathbb R \rightarrow \mathbb R$ is continuous and $h\in \mathbb R$. Let $\Delta_h^n f(x)$ be a finite difference of $f$ of order $n$, i.e

$$\Delta_h^1 f(x)=f(x+h)-f(x),$$ $$\Delta_h^2f(x)=\Delta_h^1f(x+h)-\Delta_h^1 f(x)=f(x+2h)-2f(x+h)+f(x),$$ $$\Delta_h^3 f(x)=\Delta_h^2f(x+h)-\Delta_h^2f(x)=f(x+3h)-3f(x+2h)+3f(x+h)-f(x),$$ etc. There is an explicite formula for $n$-th difference: $$\Delta_h^n f(x)=\sum_{k=0}^n (-1)^{n-k}\frac{n!}{k!(n-k)!} f(x+kh).$$

Assume now that $n\in \mathbb N$ and $f:\mathbb R \rightarrow \mathbb R$ are such that for each $x \in \mathbb R$: $$\frac{\Delta_h^n f(x)}{h^n} \rightarrow 0 \textrm{ as } h \rightarrow 0.$$ Is it then $f$ a polynomial of degree $\leq n-1$?

It is clear if $n=1$, because then $f'(x)=0$ for $x\in \mathbb R$.

Edit. Without continuity assumption about $f$ it is not true, because for $n-1$-additive function $F$ which is not $n-1$-linear we have $\Delta_h^nf(x)=0$, where $f(x)=F(x,...,x)$.

-

Let $f(x) = |x|$ then $\Delta_h^2(f)$ has support $[-2h, 0]$. In particular $\lim_{h \to 0}\Delta_h^2(f)/h^2 = 0$ pointwise, but $f$ is not a polynomial.

Edit: If the convergence in $x$ is uniform on an interval $[a, b]$ then I think that $f$ is a polynomial on that interval. This may follow from Fourier expansion, but I don't have time now to hammer out the fine points (if it can be done).

-
Very thanks for counter example. –  L.T Dec 4 '12 at 21:29
@WimC : done now. –  Ewan Delanoy Dec 7 '12 at 7:34

The result holds if we assume that $f$ is $n$-times differentiable, otherwise, as WimC shows, it's not necessarily the case.

Using this thread and translated function ($f(\cdot)=h(x+\cdot)$), we can see that $$\frac{\Delta_h^nf(x)}{h^n}=f^{(n)}(x),$$ so the hypothesis yields $f^{(n)}\equiv 0$, hence $f$ is a polynomial of degree at most $n-1$.

-
Do you use differentiability of $f$? I'm interested at most in case when $f$ is continuous. –  L.T Nov 30 '12 at 22:53

This is actually a comment too long to fit in the usual format. WimC’s claim about the uniform convergence case is correct : suppose that $\Gamma(h,x)=\frac{\Delta_h^2f(x)}{h^2} \to 0$, uniformly in $x$ on an interval $[a,b]$.

Let us put $\beta(h)={\sf sup}_{x\in[a,b]}(\big| \Gamma(h,x)\big|)$ for $h>0$. Then the hypothesis states that $\beta(h) \to 0$ when $h \to 0$.

Now, the identity

$$\Delta_{2h}^{2}f(x)=\Delta_h^{2}f(x+2h)+2\Delta_h^{2}f(x+h)+\Delta_h^{2}f(x)$$

yields

$$\Gamma(2h,x)=\frac{\Gamma(h,x+2h)+2\Gamma(h,x+h)+\Gamma(x,h)}{4}$$

Taking sups above, we see that $\beta(2h) \leq \beta(h)$. So if the bound $|\beta(h)| \leq \varepsilon$ holds for $h\in [0,\eta]$, it will also hold for $h \in [0,2\eta]$ ; it will even hold everywhere, by induction. Since this holds for every $\varepsilon >0$, we see that $\beta=0$, as wished.

-
You switched upper and lower indices? Also, I think there's a sign error since $$(\Delta_{2h}^2f)(x) = (\Delta_h^2f)(x + 2h) + 2 (\Delta_h^2f)(x + h) + (\Delta_h^2f)(x)$$ which only shows $\beta(2h) \leq 4 \beta(h)$. –  WimC Dec 7 '12 at 12:50
@WimC : YES, I did switch upper and lower indices (corrected now). YES, there was a sign error (typo). But NO, this does not change the inequality involving $\beta$, since $+$ or $-$ is immaterial when we use the triangle inequality. –  Ewan Delanoy Dec 10 '12 at 21:14
Oh, right, that factor $4$ is accounted for in $\Gamma$, sorry for the noise. Do you know if this works out for higher orders of $\Delta$? –  WimC Dec 11 '12 at 10:57