Suppose $P(n) $ is a nonconstant polynomial where all of its coefficients are nonnegative integers such that \[ \sum_{i=1}^n P(i) | nP(n+1) \]for every $n \in \mathbb{N}$. Prove that there exists an integer $k \ge 0$ such that \[ P(n) = \binom{n+k}{n-1} P(1) \]for every $n \in \mathbb{N}$.
Problem
Source: INAMO 2015 Shortlist A7
Tags: integer polynomials, algebra, polynomial
30.12.2018 18:04
We claim that $k=\deg (P)-1$ satisfied the condition. First, it's well-known that for fixed non-negative integer $n$, there exists a unique polynomial $S\in \mathbb{R}[x]$ that $\sum_{i=1}^{m}{i^n} =S(m)$ for all positive integer $m$. And also $\deg (S)=n+1$ and the leading coefficient is $1/(m+1)$. So, there exists polynomial $Q\in \mathbb{R}[x]$ with $\deg (Q)=\deg (P)+1$ and the leading coefficient of $Q$ is equal to $1/(\deg (P)+1) =1/(k+2)$ times that of $P$ that $Q(n)=\sum_{i=1}^{n}{P(i)}$ for all positive integer $n$. Hence, $Q(x)\mid xP(x+1)$ and $xP(x+1)=(k+2)Q(x)$. So, $$nP(n+1)=(k+2)\sum_{i=1}^{n}{P(i)}$$for all positive integer $n$. The conclusion can be proved by simple induction.
30.12.2018 20:15
ThE-dArK-lOrD wrote: First, it's well-known that for fixed non-negative integer $n$, there exists a unique polynomial $S\in \mathbb{R}[x]$ that $\sum_{i=1}^{m}{i^n} =S(m)$ for all positive integer $m$.. Thanks. But may i ask why is this true?
01.01.2019 18:40
GorgonMathDota wrote: Thanks. But may i ask why is this true? The uniqueness is clear since two distinct polynomials can only coincide at finitely many points (otherwise the difference would be a non-zero polynomial with infinitely many zeroes which is impossible). One way to show that these polynomial exist is to first note that for fixed $n$, one can write $x^n$ as a linear combination of binomial coefficients in $x$. E.g. $x^2=2\binom{x}{2}+\binom{x}{1}$. This is easy to prove by induction (if you know what this means: Both the monomials $x^n$ and the polynomials $\binom{x}{n}$ form a basis of the polynomial ring $\mathbb{R}[x]$ as a vector space. In fact any sequence $P_n$ of polynomials with $\deg P_n=n$ would do the job). That reduces the problem to finding a polynomial expression for $\sum_{i=1}^m \binom{i}{n}$. But that is much easier because we can find that polynomial on the nose: It is equal to $\binom{m+1}{n+1}$ by some elementary combinatorial identity (e.g. use induction and in the induction step use the recurrence formula from Pascal's Triangle). Edit: These polynomials are known as the Faulhaber Polynomials.