Does there exist any non-zero polynomial $f:\mathbb C \to \mathbb C$ such that $f(x+2)-2f(x+1)=f(x) , \forall x \in \mathbb C$?

Question

Does there exist any non-zero polynomial $f:\mathbb C \to \mathbb C$ such that $$f(x+2)-2f(x+1)=f(x) , \forall x \in \mathbb C?$$

Beyond this specific example, what are general methods to decide if such a recurrence can be satisfied by a polynomial?

Answer 1

No polynomial can satisfy a linear recurrence except in trivial cases because the solution of linear recurrences is a combination of geometric progressions.

For instance, $f(n+2)-2f(n+1)=f(n)$ for all $n \in \mathbb N$ implies that $$f(n) = c_1 (1-\sqrt2)^n+c_2 (1+\sqrt2)^n$$ where $c_1, c_2$ are parameters determined by $f(0)$ and $f(1)$.

Indeed, $f(n) \sim c_2 (1+\sqrt2)^n$ as $n \to \infty$, but a polynomial grows as $\sim a n^d$.

Answer 2

Generalization

Theorem. Let $K$ be an algebraically closed field of characteristic $0$ and $V$ the $K$-vector space of functions from $\mathbb{Z}_{\geq 0}=\{0,1,2,\ldots\}$ to $K$. The $K$-linear operator $T:V\to V$ is defined by $$(T\varphi)(k):=\varphi(k+1)$$ for all $\varphi\in V$. Then, for each nonzero polynomial $P(X)\in K[X]$ of degree $p$ such that $P(0)\neq 0$, the kernel of the $K$-linear map $P(T):V\to V$, where $$P(T):=\varpi_p\,T^p+\varpi_{p-1}\,T^{p-1}+\ldots+\varpi_1\,T+\varpi_0\,I$$ if $P(X)=\sum\limits_{\rho=0}^p\,\varpi_\rho\,X^\rho$ and $I$ denotes the identity map on $V$, is of dimension $p$ over $K$ and it is spanned by functions of the form $k\mapsto k^\mu\,\lambda^k$ for all $k=0,1,2,\ldots$ where $\lambda$ is a root of $P(X)$ and $\mu$ is a nonnegative integer less the multiplicity of $\lambda$ as a root of $P(X)$.

To prove the theorem, we first note that, for all $\lambda\in K$, $T-I$ and $T-\lambda \,I$ are similar linear transformations. Define for each $\xi\in K\setminus\{0\}$ the linear transformation $M_\xi:V\to V$ via $\left(M_\xi\varphi\right)(k):=\xi^k\,\varphi(k)$ for all $k\in\mathbb{Z}_{\geq 0}$. Then, we see that $$T-\lambda \,I= M_{\lambda}\circ (T-I)\circ M_{\lambda^{-1}}\,.$$

The rest is the standard routine. First, factorize $$P(X)=\varrho\,\prod_{i=1}^r\,\left(X-\lambda_i\right)^{m_i}\,,$$ where $\lambda_1,\lambda_2,\ldots,\lambda_r\in K$ are pairwise distinct, $\varrho\in K$ with $\varrho\neq 0$, and $m_i$ is the multiplicity of $X-\lambda_i$ in $P(X)$ for $i=1,2,\ldots,r$. It follows (with quite some details to fill in, which are based on the fact that, for every $j=1,2,\ldots,r$, $\left(X-\lambda_j\right)^{m_j}$ and $\prod\limits_{i\in\{1,2,\ldots,r\}\setminus\{j\}}\,\left(X-\lambda_i\right)^{m_i}$ are relatively prime polynomials) that $$\ker\big(P(T)\big)=\bigoplus_{i=1}^r\,\ker\big(\left(T-\lambda_i\,I\right)^{m_i}\big)\,.$$

It is easily seen that $\ker\big(\left(T-\lambda\,I\right)^m\big)=M_\lambda\Big(\ker\big((T-I)^m\big)\Big)$ for every nonzero $\lambda\in K$ and $m\in\mathbb{Z}_{\geq0}$. The theorem is now evident, as $\ker\big((T-I)^m\big)$ is precisely the space of $K$-valued polynomial functions on $\mathbb{Z}_{\geq 0}$ of degree less than $m$.

Corollary. With the same setting as in the theorem above, for every positive integer $s$, the kernel of $T^s\,P(T)$ is direct sum of the kernel of $P(T)$ and the kernel of $T^s$, which is $s$-dimensional over $K$ and spanned by functions of the form $k\mapsto \delta_{k,j}$ for all $k\in\mathbb{Z}_{\geq 0}$ and for each $j=0,1,2,\ldots,s-1$. Here, $\delta$ is the Kronecke delta. Therefore, $\ker\big(T^s\,P(T)\big)$ is a $(p+s)$-dimensional $K$-vector subspace of $V$.

Remark. If the field $K$ in the theorem and the corollary above is not assumed to be algebraically closed, then it remains true that the kernel of $P(T)$ is a $p$-dimensional $K$-vector subspace of $V$, for every nonzero polynomial $P(X)\in K[X]$ of degree $p$.

---

We still keep the setup from the theorem above. If $K$ is not assumed to be algebraically closed and is now allowed to have a positive characteristic $\kappa$, then we can replace $V$ by the $K$-vector space of functions from $\mathbb{F}_\kappa\to K$, where $\mathbb{F}_\kappa$ is the prime subfield of $K$. If $P(X)$ is a nonzero polynomial of degree $p<\kappa$ such that $P(0)\neq 0$, then let $m$ be the multiplicity of $X-1$ as a factor of $P(X)$. The left-shift map $T:V\to V$ is defined in the same way. It follows that the kernel of $P(T):V\to V$ is an $m$-dimensional $K$-vector subspace of $V$ and consists of maps of the form $k\mapsto f(k)$, where $f(X)\in K[X]$ is a polynomial of degree less than $m$. (If $P(0)=0$, we can write $P(X)=X^s\,\tilde{P}(X)$ for some nonzero $\tilde{P}(X)\in K[X]$ with $\tilde{P}(0)\neq 0$ and arrive at the same conclusion by studying $\tilde{P}(T)$ instead of $P(T)$.)

---

Proposition. Let $K$ be a field of characteristic $0$. Let $f\in K[X]$ be such that, for some nonnegative integer $n$, $a_0,a_1,a_2,\ldots,a_n\in K$ with $a_n\neq 0$, and $g(X)\in K[X]$ is of degree less than or equal to $d\in\mathbb{Z}_{\geq 0}$, we have $$\sum_{i=0}^n\,a_i\,f(k+i)=g(k)\tag{*}$$ for every nonnegative integer $k$. Then, the degree of $f(X)$ is at most $d+m$, where $m$ is the multiplicity of $1$ as a root of the polynomial $\sum\limits_{i=0}^n\,a_i\,X^i$. When $g(X)$ is nonzero and precisely of degree $d$, this bound on the degree of $f(X)$ is sharp, and there exists a unique polynomial $\tilde{f}(X)\in K[X]$ of the form $\tilde{f}(X)=\sum\limits_{i=m}^{m+d}\,c_i\,X^i$ with $c_m,c_{m+1},c_{m+2},\ldots,c_{m+d}\in K$ such that $f(X)=\tilde{f}(X)$ is a solution to (*), and other solutions are given by $f(X)=\tilde{f}(X)+q(X)$ where $q(X)\in K[X]$ is an arbitrary polynomial of degree at most $m-1$.

Proof. We shall assume that $a_0\neq 0$. Otherwise, let $\nu$ is the smallest element of $\{0,1,2,\ldots,n\}$ such that $a_\nu\neq 0$. Then the equality $\sum\limits_{i=\nu}^n\,a_i\,f(k+i)=g(k)$ holds for all $k=0,1,2,\ldots$, which then mean that it gives rise to a polynomial equation $\sum\limits_{i=\nu}^n\,a_i\,f(X+i)=g(X)$. Ergo, we also have $$\sum\limits_{i=0}^{n-\nu}\,a_{i+\nu}\,f(k+i)=g(k-\nu)$$ for all $k=0,1,2,\ldots$.

Let $b_0,b_1,b_2,\ldots,b_{n+d+1}\in K$ be such that $$h(X):=\sum_{i=0}^{n+d}\,b_i\,X^i=(X-1)^{d+1}\,\sum_{i=0}^n\,a_i\,X^i\,.$$ Therefore, $f$ satisfies $$\sum_{i=0}^{n+d+1}\,b_i\,f(k+i)=0$$ for all $k=0,1,2,\ldots$.

Let $\lambda_1,\lambda_2,\ldots,\lambda_r$, and $1$ be distinct roots of $h$ in the algebraic closure $\bar{K}$ of $K$ with multiplicities $m_1,m_2,\ldots,m_r$, and $m+d+1$, respectively. Due to the theorem above, there exist polynomials $\phi_1(X),\phi_2(X),\ldots,\phi_r(X)$, and $\phi(X)$ in $\bar{K}[X]$ of degrees less than $m_1,m_2,\ldots,m_r$, and $m+d+1$, respectively, such that $$f(k)=\sum_{j=1}^r\,\phi_j(k)\,\lambda_j^k+\phi(k)$$ for all $k=0,1,2,\ldots$. That is, $$\sum_{j=1}^r\,\phi_j(k)\,\lambda_j^k+\big(\phi(k)-f(k)\big)=0\,.$$ By the theorem above, $\phi_1(X),\phi_2(X),\ldots,\phi_r(X)$, and $\phi(X)-f(X)$ are all the zero polynomial. That is, $f(X)=\phi(X)$ is of degree at most $m+d$.

The remaining part of the proposition is not difficult to prove (albeit tedious). It only involves solving (non-degenerate) systems of linear equations.

Corollary. With the same setup as the proposition above, suppose that $g(X)$ is the zero polynomial. If $1$ is not a root of $\sum\limits_{i=0}^n\,a_i\,X^i$, then $f(X)$ is the zero polynomial. If $1$ is a root of $\sum\limits_{i=0}^n\,a_i\,X^i$ with multiplicity $m$, then $f(X)$ can be any polynomial of degree at most $m-1$.

---

To answer the OP's question, we use the proposition with $K=\bar{K}=\mathbb{C}$. Then, we have $g(X)=0$ and $n=2$ with $a_0=-1$, $a_1=-2$, and $a_2=1$. The multiplicity of $X-1$ in $a_2\,X^2+a_1\,X+a_0$ is $0$. The degree of $g(X)$ is less than or equal to $d:=0$ (technically, it is $-\infty$). Therefore, $f(X)$ must be constant. It follows immediately that $f(X)$ is the zero polynomial. It is also a trivial consequence from the newly inserted corollary of the proposition.

Answer 3

The equation says

$\Delta^2 f(x) = 2f(x)$

where $\Delta=\Delta_{+1}$ is the finite difference operator $\Delta f = f(x+1) - f(x)$.

Thus $\Delta^k$ does not kill $f$ no matter how large $k$ is, so $f$ cannot be a polynomial.

General case. A linear recursion on $f(x)$ is consistent with it being a polynomial if and only if it is equal to the result of taking some linear relation satisfied by the $0$ function, and applying a finite sequence of difference operators $\Delta_a \circ \Delta_b \circ ...$ to that. This does not assume the shifts $a,b,...$ are integers.

Answer 4

(1). If $ f(x)=\sum_{j=0}^mA_jx^j $ with constant(s) $ A_0,..., A_m $ such that $ A_m\ne 0, $ then for $ x\ne 0 $ we have $ f(x)=A_mx^m(1+g(x)) $ where $ \lim_{|x|\to \infty}g(x)=0. $

(2). By binomially expanding each term in the expressions for $ f(x+2) $ and for $ f(x+1) $ we have $ f(x+2)-f(x+1)=\sum_{j=0}^mB_jx^j $ with constant(s) $ B_0,...,B_m $ such that $ B_m=-A_m. $ So for $ x\ne 0 $ we have $ f(x+2)-2f(x+1)=-A_mx^m(1+h(x)) $ where $ \lim_{|x|\to \infty} h(x)=0. $

(3). So for all sufficiently large $ n\in N, $ both sides of the recurrence equation are non-zero and the LHS divided by the RHS is $ -(1+h(n))/(1+g(n)) $ which tends to $ -1 $ as $ n\to \infty. $ .... The next paragraph shows another method.

(4). We can also observe from the first sentence of (2) that $ e(x)=f(x+2)-2f(x+1)-f(x) $ is a polynomial of degree $ m $ with leading co-efficient $ -2A_m\ne 0, $ so the equation $ e(x)=0 $ has at most $ m $ solutions.

Answer 5

$f(x+2) = f(x) + 2f(x+1)$

Suppose that $f(x)$ is a polynomial of degree $n \ge 1$.

We will use the notation $g_m(x)$ to represent a polynomial of degree at most $n-1$ (whos coefficients we really don't care about).

Then, for some $a \ne 0$,

\begin{align} f(x) &= ax^n + g_0(x) \\ f(x+1) &= ax^n + g_1(x) \\ f(x+2) &= ax^n + g_2(x) \\ \hline f(x+2) = f(x) + 2f(x+1) &\implies \\ ax^n + g_2(x) &= 3ax^n + g_4(x)\\ a &= 0 \end{align}

So there is no such polynomial.