XIII OBM

Rewrite the equation as $\frac{n(a_{n+2}-a_{n+1})}{a_n}=k$. If $a_n$ is a polynomial in $n$, say $a_n=r(n)={\sum }_{i=0}^d{r}_i{n}^i$, then the limit ${\lim }_{n\to \infty }\frac{n(a_{n+2}-a_{n+1})}{a_n}$ must exist and be equal to $k$. But $$\begin{array}{rl}& \underset{n\to \infty }{\lim }\frac{n(a_{n+2}-a_{n+1})}{a_n}\\ & =\underset{n\to \infty }{\lim }\frac{n\left({\sum }_{i=0}^d{r}_i(n+2{)}^i-{\sum }_{i=0}^d{r}_i(n+1{)}^i\right)}{{\sum }_{i=0}^d{r}_i{n}^i}\\ & =\underset{n\to \infty }{\lim }\frac{n{\sum }_{i=0}^d{r}_i((n+2{)}^i-(n+1{)}^i)}{{\sum }_{i=0}^d{r}_i{n}^i}\\ & =\underset{n\to \infty }{\lim }\frac{n{\sum }_{i=0}^d{r}_i((n+2{)}^{i-1}+(n+2{)}^{i-2}(n+1)+\cdots +(n+1{)}^{i-1})}{{\sum }_{i=0}^d{r}_i{n}^i}\\ & =\underset{n\to \infty }{\lim }\frac{n^d{\sum }_{i=0}^d{r}_i{n}^{i-d}\left({\left(1+\frac{2}{n}\right)}^{i-1}+{\left(1+\frac{2}{n}\right)}^{i-2}\left(1+\frac{1}{n}\right)+\cdots +{\left(1+\frac{1}{n}\right)}^{i-1}\right)}{n^d{\sum }_{i=0}^d{r}_i{n}^{i-d}}\\ & =\underset{n\to \infty }{\lim }\frac{r_d\left({\left(1+\frac{2}{n}\right)}^{d-1}+{\left(1+\frac{2}{n}\right)}^{d-2}\left(1+\frac{1}{n}\right)+\cdots +{\left(1+\frac{1}{n}\right)}^{d-1}\right)}{r_d}=d\end{array}$$ So if $a_n$ is a polynomial in $n$ then $k$ is the degree of $a_n$ and is a nonnegative integer.

Now we need to show an example of polynomial $r_k(n)$ for each nonnegative integer $k$. For $k=0$ and $k=1$, one may consider $r_0(n)=0$ and $r_1(n)=n$. For $k\ge 2$, let's find a polynomial $$r(n)=n^k+r_{k-1}{n}^{k-1}+\cdots +r_{1}n+r_0$$ such that $n(r(n+2)-r(n+1))=kr(n)$ for all $n$. Expanding $(n+2{)}^i$ and $(n+1{)}^i$ via binomial theorem, we obtain the system of equations $$\begin{array}{rl}& 3\left(\genfrac{}{}{0ex}{}{k}{k-2}\right)+\left(\genfrac{}{}{0ex}{}{k-1}{k-2}\right)r_{k-1}=k{r}_{k-1}\\ & 7\left(\genfrac{}{}{0ex}{}{k}{k-3}\right)+3\left(\genfrac{}{}{0ex}{}{k-1}{k-3}\right)r_{k-1}+\left(\genfrac{}{}{0ex}{}{k-2}{k-3}\right)r_{k-2}=k{r}_{k-2}\\ & \dots \\ & (2^j-1)\left(\genfrac{}{}{0ex}{}{k}{k-j}\right)+(2^{j-1}-1)\left(\genfrac{}{}{0ex}{}{k-1}{k-j}\right)r_{k-1}+\cdots +\left(\genfrac{}{}{0ex}{}{k-j+1}{k-j}\right)r_{k-j+1}=k{r}_{k-j+1}\\ & \dots \end{array}$$ Since $\left(\genfrac{}{}{0ex}{}{k-j+1}{k-j}\right)=k-j+1\ne k$ it is possible to find $r_{k-j+1}$ in each equation and the system is possible, so there is such a polynomial.

For the second part, rewrite the given equation as $n\left(\frac{a_{n+2}}{a_{n+1}}-1\right)=k\frac{a_n}{a_{n+1}}$. If there exists polynomials $p$ and $q$ such that $\frac{a_{n+1}}{a_n}=\frac{p(n)}{q(n)}$, then $$n\left(\frac{p(n+1)}{q(n+1)}-1\right)=k\frac{q(n)}{p(n)}⟺n(p(n+1)-q(n+1))p(n)=kq(n+1)q(n)$$ We may suppose without loss of generality that $p(n)$ and $q(n)$ don't have common factors. Let $m$ and $m^{\prime }$ be the degrees of $p$ and $q$, respectively. If $m=m^{\prime }$ then the right hand side has degree $2m$ and the degree of $p(n+1)-q(n+1)$ is $m-1$. This means that the leading coefficients of $p$ and $q$ are equal. Since $p(n)$ and $q(n)$ don't have common factors, $p(n)$ divides $q(n+1)$, which in this case means $p(n)=q(n+1)$. Substituting yields $n(q(n+2)-q(n+1))=kq(n)$, and $q$ satisfies the first part of the problem, and thus $k$ must be a nonnegative integer.

If $m\ne m^{\prime }$ by checking degrees we must have $1+\max (m,m^{\prime })+m=2m^{\prime }\Rightarrow 2m^{\prime }\le 1+m+m^{\prime }⟺m<m^{\prime }\Rightarrow 1+m^{\prime }+m=2m^{\prime }⟺m^{\prime }=m+1$. The polynomials $q(n+1)$ and $p(n+1)-q(n+1)$ don't have common factors, so $q(n)$ divides $p(n+1)-q(n+1)$. These two polynomials have both degree $m^{\prime }$ and opposite leading coefficients, so $p(n+1)=q(n+1)-q(n)$. Substituting yields the polynomial identity $n(q(n)-q(n-1))=-kq(n+1)$. Now if $r(n)=q(1-n)$ and $m=-n$ then $n(r(m+2)-r(m+1))=-kr(m)$ and we reduce the problem to the first part again for $-k$ instead of $k$. So, in this case, $k$ must be a nonpositive integer.

Conversely, it's not hard to obtain $p(n)$ and $q(n)$ from the above case, so the answer for the second part is $k$ integer.