Prove that for any polynomial $P(x)$ there exist polynomials $F(x)$ and $G(x)$ such that $F\left(G(x) \right)-G\left(F(x) \right)=P(x)$

I am assuming that you are working on $\mathbb{R}$, $\mathbb{C}$, or any field of characteristic $0$. Write $$P(x)+1=\sum_{r=0}^k\,c_r\,\binom{x}{r}$$ for some nonnegative integer $k$ and for some constants $c_0,c_1,\ldots,c_k$. (These constants exist because $\binom{x}{r}$ for $r=0,1,2,\ldots$ span the vector space of polynomials in $x$.) Show that $$F(x):=\sum_{r=0}^k\,c_r\,\binom{x}{r+1}$$ satisfies the condition $F(x+1)-F(x)=P(x)+1$. Here, $$\binom{x}{r}=\frac{x(x-1)(x-2)\cdots(x-r+1)}{r!}$$ for $r=0,1,2,\ldots$.

Hint: Verify that $\displaystyle \binom{x+1}{r+1}=\binom{x}{r+1}+\binom{x}{r}$ for every $r=0,1,2,\ldots$.

P.S.: I would be really interested to see whether the statement still holds if the field is of a positive characteristic.


A solution different from the (excellent) solution of Batominovski (in characteristic zero). Let $E_n$ be the space of the polynomials of degree $\leq n$. Choose $n>$ the degree of $P$. Then the map $T$ defined by $$T(Q)=Q(x+1)-Q(x)$$ is a linear surjective application from $E_n$ to $E_{n-1}$, as the image of the polynomial $x^m$ for $m\geq 1$ is $$U_m=(x+1)^m-x^m=mx^{m-1}+\ldots$$ and clearly the polynomials $U_m$, for $m=1,\cdots,n$, is a basis of $E_{n-1}$. As $1+P$ is in $E_{n-1}$, we are done.


Hint $\ $ Just like the derivative, the linear operator $\, D f(x) = f(x\!+\!1) - f(x) \,$ acts on polynomials by decreasing the degree by $1,\,$ since $\,D x^n = (x+1)^n-x^n = c_n x^{n-1} +g(x)\,$ with $\,c_n\neq 0,\,\deg g < n-1$. For any such linear operator one can solve equations of the form $\, D f(x) = g(x)\,$ for given polynomial $g$ by using undetermined coefficients and induction, e.g.

$$ g_n x^n+\cdots = D (f_{n+1} x^{n+1} + \cdots) = c_{n+1} f_{n+1} x^n + \cdots\,\Rightarrow\, f_{n+1} = g_n/c_{n+1}$$

Substituting that value for $\,f_{n+1}\,$ we reduce to a problem with smaller degree $\,g$