Recently I came across a functional equation which always has a polynomial with integer coefficients solution.


Let
$$
L\_n(x)=(2 x+1)^2f(x+1)-4x(x+n+1)f(x)-((2 n+1)!!)^2\prod\_{i=1}^n(x+i).
$$
**Problem:**
For any positive integer $n$, there exists a polynomial $f(x) $with integer coefficients of order $n$ satisfying 
$$
L\_n(x)=0.
$$
How to prove this question? Or can we find the solution to the above equation?


For $n=1$, the solution is $5x+4$.


For $n=2$, the solution is $89x^2+233x+128$.


For $n=3$, the solution is $3429x^3+18675x^2+30222x+13824$.


Hints, references and proof are all welcome!



Integer Polynomial solutions to functional equation
Note that $L(f):=(2x+1)^2f(x+1)-4x(x+n+1)f(x)$ is a linear operator which maps the $\mathbb{Q}$-linear space $\pi\_n$ of polynomials $h(x)\in \mathbb{Q}[x]$ of degree at most $n$ to itself. Assume that $L(f)=0$. Substituting $x=0$ we get $f(1)=0$, then substituting $x=1$ we get $f(2)=0$ and so on, thus $f\equiv 0$. So, $L$ is invertible linear transform of $\pi\_n$, therefore there exists unique $f\in \pi\_n$ for which $L(x)=((2n+1)!!)^2\prod\_{i=1}^n (x+i)$. It remains to prove that $f$ has integer coefficients and degree of $f$ equals $n$. 


For proving that $f$ has integer coefficients we prove that $f(k)$ is an integer divisible by $n!$ for $k=1,2,\dots,n+1$. It implies that $f\in \mathbb{Z}[x]$, that may be seen, for example, from Lagrange interpolation formula:
$$
f(x)=\sum\_{k=1}^{n+1}f(k)\prod\_{j\in \{1,\dots,n+1\}\setminus k}\frac{x-j}{k-j}.
$$
We may prove by induction in $k$ that $f(k)/n!$ is an integer divisible by $(2k+1)^2(2k+3)^2\dots (2n+1)^2$ for all $k=1,\dots,n+1$. Base $k=1$ follows from substituting $x=0$, induction step is straightforward (substitute $x=k$).


It remains to prove that $\deg f=n$. But if $\deg f(x)<n$, then comparing coefficients of $x^n$ we get that in $L(f)$ this coefficient is divisible by 4, while in RHS it is not.


