# Functions satisfying $\sum_{n=0}^k(-1)^n\binom{k}{k-n}f^{k-n}(x)=0$.

This question was motivated by this one. Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a continuous function. Define $f^n(x)=f\circ f\circ\cdot\cdot\cdot\circ f$, $n$ times, $f^0(x)=x$ and $k\geq 2$ a integer. Suppose that $f$ satisfies the equation: $$\tag{1}\sum_{n=0}^k(-1)^n\binom{k}{k-n}f^{k-n}(x)=0$$

Note that for each fixed $a\in\mathbb{R}$, $f_a(x)=x+a$ satisfies $(1)$. Are the only solutions of $(1)$ of the form $f_a$ for some $a$? Also note that $f_a$ is an solution of the equation $$\tag{2}(f-I)^k(x)=a$$

The same question applies here: Is the only solution of $(2)$ of the form $f_a$? If we let $a$ vary in $(2)$, we get a family of equations. Is that family of equations equivalently to $(1)$?

-
Note that you changed your notation in $(1)$: we usually define $f^{(m)}$ as the derivative of order $m$ of the function $f$. –  Pedro Tamaroff Mar 13 '13 at 1:23
@PeterTamaroff, thank you, let me fix it. –  Tomás Mar 13 '13 at 11:35
It is plain to observe that $f$ must be an increasing bijection onto $\Bbb{R}$. But except the case $n=2$, where the solution was already dealt in the link above, I have no idea what the answer would be. –  sos440 Mar 13 '13 at 13:44

I first tried to modify the proof at the link in the question, but soon I realized that the proof holds because of the particular form satisfied in the case $n = 2$.

Proposition. Let assume that a continuous function $f : \Bbb{R} \to \Bbb{R}$ satisfies $$\sum_{k=0}^{n} \binom{n}{k} (-1)^{n-k} f^k (x) = a, \quad \forall x \in \Bbb{R} \tag{1}$$ for some real number $a \in \Bbb{R}$ and some integer $n \geq 1$. If we further assume that $f$ has at least one fixed point, then $f$ is the identity function.

We first observe the following properties.

Lemma 1. Let $f$ be a continuous function satisfying $(1)$. That is, let $f$ satisfy the assumption of Proposition except that $f$ has a fixed point. Then $f$ is an increasing bijection from $\Bbb{R}$ onto $\Bbb{R}$.

Proof. Assume $f(x) = f(y)$. Then

$$x = (-1)^n a - \sum_{k=1}^{n} \binom{n}{k} (-1)^{k} f^k (x) = (-1)^n a - \sum_{k=1}^{n} \binom{n}{k} (-1)^{k} f^k (y) = y$$

and $f$ is injective. In particular, $f(\Bbb{R})$ is an open interval.

To prove the surjectivity of $f$, assume that $f$ is not surjective. Then either $\sup f$ or $\inf f$ is finite, and in any cases we can find a real number $\alpha \in \Bbb{R}$ and a sequence of real numbers $x_j$ such that $|x_j| \to \infty$ and $f(x_j) \to \alpha$ as $j \to \infty$. But this implies

\begin{align*} \infty = \lim_{j\to\infty} \left| x_j \right| = \lim_{j\to\infty} \left| (-1)^n a - \sum_{k=1}^{n} \binom{n}{k} (-1)^{k} f^k (x_j) \right| = \left| (-1)^n a - \sum_{k=1}^{n} \binom{n}{k} (-1)^{k} f^{k-1}(\alpha) \right| < \infty, \end{align*}

a contradiction. Therefore $f$ is surjective. In particular, $f$ is a homeomorphism and it is either increasing or decreasing.

To prove that $f$ is increasing, assume that $f$ is decreasing. Then $(-1)^{k-1} f^{k}$ is decreasing for any $k \geq 1$. Thus the right-hand side of

$$x = (-1)^n a + \sum_{k=1}^{n} \binom{n}{k} (-1)^{k-1} f^k (x)$$

is also decreasing, a contradiction. This completes the proof. ■

Lemma 2. Suppose that $f : \Bbb{R} \to \Bbb{R}$ be an continuous increasing bijection, so that it extends to a continuous bijection $\bar{f}$ from $\bar{\Bbb{R}} = [-\infty, \infty]$ onto $\bar{\Bbb{R}}$. Then for any $x \in \bar{\Bbb{R}}$, we have the following trichotomy:

1. If $x < f(x)$, then $f^k (x)$ converges to the smallest fixed point of $\bar{f}$ greater than $x$.
2. If $x > f(x)$, then $f^k (x)$ converges to the greatest fixed point of $\bar{f}$ smaller than $x$.
3. If $x = f(x)$, then $f^k (x)$ converges to $x$.

Proof. Since $\bar{f} : \bar{\Bbb{R}} \to \bar{\Bbb{R}}$ is continuous, the set $F = \{ \bar{f}(x) = x : x \in \bar{\Bbb{R}} \}$ is a closed set containing both $\infty$ and $-\infty$. If $F = \bar{\Bbb{R}}$, there is nothing to prove and assume that $F^c \neq \varnothing$. Since $F^c$ is open in $\Bbb{R}$, we can decompose it as a countable union of disjoint open intervals $U_j$. Note that on each $U_j$, either $f(x) > x$ identically for all $x \in U_j$ or $f(x) < x$ identically for all $x \in U_j$ by continuity of $f$.

Now let $x \neq f(x)$. Then $x \in U_j$ for some $j$. Assume first that $x < f(x)$. Then for any $x < y \leq f(x)$, we have $f(y) > f(x) \geq y$ and we have $[x, f(x)] \subset U_j$. In particular, $f(x) \in U_j$. Now this argument can be repeatedly applied to yield that $f^k (x) \in U_j$ for all $k$. Since $f^k(x)$ is monotone increasing, it must converge to some point $\alpha \in \bar{\Bbb{R}}$. It is plain to check that $\alpha = \sup U_j$ and $\alpha$ is a fixed point of $\bar{f}$, proving the first option of the trichotomy. The second option follows exactly the same manner and the third option is trivial. ■

As an immediate consequence, we obtain the following corollary:

Corollary. If $f : \Bbb{R} \to \Bbb{R}$ is a continuous increasing bijection having at least one fixed point, then for any $x \in \Bbb{R}$, either $f^k (x)$ or $f^{-k} (x)$ converges to a fixed point of $f$.

Proof. Let $U_j$ be as in the proof above. If $x \in U_j$, then $f^k (x)$ and $f^{-k} (x)$ converges to $\sup U_j$ and $\inf U_j$. Since $f$ has a fixed point, either $\sup U_j$ or $\inf U_j$ is finite. ■

Now we are ready to prove the proposition.

Proof of Proposition. Define

$$g(x) = \sum_{k=0}^{n-1} \binom{n-1}{k} (-1)^{n-1-k} f^k (x).$$

It is plain to observe that $g \circ f - g = a$. Let $F$ be the set of fixed points of $f$. Then $F$ is non-empty by assumption. If we pick a point $\alpha \in F$, then

$$0 = g(f(\alpha)) - g(\alpha) = a.$$

In particular, we have

$$g = g\circ f = g \circ f^{k} \quad \forall k \in \Bbb{Z}.$$

Thus if $n = 1$, then $g(x) = x$ and this identity immediately yields $f(x) = x$. This shows that we may assume $n \geq 2$.

In view of the corollary above, for each $x \in \Bbb{R}$, either $f^{k}(x)$ or $f^{-k}(x)$ converges to a point of $F$. Thus there exists $\alpha \in F$ such that

$$g(x) = g(\alpha) = 0,$$

where the last inequality holds by the definition of $g$ together with the assumption $n \geq 2$. Putting together, we showed that if $(1)$ holds for some $n \geq 2$ and $a \in \Bbb{R}$, then $(1)$ also holds for $n-1$ instead of $n$ and $a = 0$. Therefore by the mathematical induction, we obtain the desired conclusion. ■

-

Let $P\in\Bbb R[X]$ be a polynomial of degree${}<k$, such that its polynomial function $p:\Bbb R\to\Bbb R$ is nowhere decreasing (in other words $p'(x)\geq0$ for all $x\in\Bbb R$; this obviously requires $\deg P$ to be odd). Then $p^{-1}$ is well defined and continuous. Define $f:x\mapsto p(p^{-1}(x)+1)$ which is also continuous, and satisfies $f^n(p(x))=p(x+n)$ for all $n$. Now $$\sum_{i=0}^k(-1)^i\binom k{k-i}f^{k-i}(p(x)) =\sum_{i=0}^k(-1)^i\binom kip(x+k-i) =\Delta^k(p)(x+k) =0$$ for all $x\in\Bbb R$, where $\Delta$ is a finite difference operator defined by $\Delta g: x\mapsto g(x)-g(x-1)$, which decreases the degree of polynomial functions, so that $\Delta^k(p)=0$ identically.

Since $p$ is surjective this shows $f$ satisfies your requirement and that the answer to your first question is negative for $k\geq4$. The simplest counterexample is $f:x\mapsto (\sqrt[3]x+1)^3$.

-
Interesting. Please, let me ask you two things. 1 - Can you spot the error in the proof of @sos440? 2 - Any suggestion about the case $k=3$? Thank you. –  Tomás Mar 19 '13 at 12:06
I'm not sure there is an error in the proofs by @sos440, since all the significant statments there require that $f$ have a fixed point, and the function defined in my answer never have a fixed point. –  Marc van Leeuwen Mar 19 '13 at 12:31
As for the case $k=3$, the method described here gives counterexamples defined on $\Bbb R_{\geq0}$, for instance $x\mapsto(\sqrt x+1)^2=x+2\sqrt x+1$, but not functions defined on all of $\Bbb R$. I think I can prove that there aren't any continuous non-affine functions $f:\Bbb R\to\Bbb R$ that satisfy $x-3f(x)+3f^2(x)-f^3(x)=0$ for all $x$. –  Marc van Leeuwen Mar 19 '13 at 12:40
You are right, I forgot he assumend a fixed point. –  Tomás Mar 19 '13 at 12:49
(+1) This is quite simple yet suggesting! –  sos440 Mar 19 '13 at 13:21

Consider a case $k = 2$: $$f(f(x)) - 2f(x) + x = 0$$ Let $f(x) = x + g(x)$, then $$g(x) = g(x + g(x))$$ For example, $$g(\frac{x}{n}) = g(\frac{x}{n} + g(\frac{x}{n})) = ... = g(x + g(\frac{x}{n}))$$

Assuming that $g$ is contiguous at $0$, $g(x + g(0)) = g(0)$ for any $x$, that is, $g$ is a constant indeed. The similar mechanics works for other $k$ as well.

I don't know how to approach it without a contiguity assumption.

-
The function $f$ is continuous. –  Tomás Mar 12 '13 at 22:07
Can you explain me how do you prove that $g(\frac{x}{n})=g(x+g(\frac{x}{n}))$? –  Tomás Mar 12 '13 at 22:39
If you think that "The similar mechanics works for other $k$ as well", you should demonstrate it. It doesn't work in the same way, see my answer. –  Marc van Leeuwen Mar 19 '13 at 13:19