Computations suggest that the polynomials $$p_n(x)=\prod_{k=1}^n \left(\frac{x+k}{k}\right)^{\min(k,n-k)}$$ are integer valued. Is there a simple proof of this fact?

Edit For a positive integer $m$ this reduces to $$p_n(m)=\prod_{j=0}^{m-1}\frac{j!(n+j)!}{(\lfloor\frac{n}{2}\rfloor+j)! (\lfloor\frac{n+1}{2}\rfloor+j)!}.$$

Edit 2: A polynomial $p(x)$ is called integer-valued if $p(k)\in\mathbb{Z}$ for $k\in\mathbb{Z}.$

In the mean-time I have found that $p_n(m)= (-1)^{n\lfloor{\frac{m}{2}}\rfloor}\det \left( {p_{n+i+j}(1) } \right)_{i,j = 0}^{m - 1}$. Since $p_n(1)=\binom{n}{\lfloor{\frac{n}{2}}\rfloor}$ is an integer this implies that $p_n(x)$ is integer- valued. But I am interested in a simple direct proof of this fact.

  • 1
    $\begingroup$ Show that $\sum_{k\in [1,n],p^r | k+x} \min(k,n-k) \ge \sum_{k\in [1,n], p^r | k} \min(k,n-k)$ $\endgroup$
    – reuns
    Apr 2, 2021 at 16:58
  • $\begingroup$ Define "integer valued". $\endgroup$
    – K.defaoite
    Apr 6, 2021 at 0:07
  • $\begingroup$ Can you elaborate? $\prod_{k=1}^2 ((x+k)/k)^{\min\{k,n-k\}}$ is the polynomial $$\left(x+1\right)\left(\frac{x+2}{2}\right)^0$$ which is just $x+1$. $\endgroup$
    – William
    Apr 6, 2021 at 0:51
  • $\begingroup$ @William Yes, of course. $p_n(x)$ can also be written $p_n(x)=\prod_{k=1}^{n-1} \left(\frac{x+k}{k}\right)^{\min(k,n-k)}.$ $\endgroup$ Apr 6, 2021 at 6:29
  • $\begingroup$ One can also write $p_n(x)=\prod_{d=1}^{n/2}\prod_{k=d}^{n-d}\frac{x+k}{k}$, but I don't immediately see if it is any helpful (inner product is not always an integer so probably not..). $\endgroup$
    – Sil
    Apr 6, 2021 at 10:18

1 Answer 1


A standard approach to the analogous question for binomial coefficients is to count the number of copies of each prime in the numerator and denominator and to show that the numerator never loses.

That approach works here, though the details are quite a bit messier. It is a little cleaner to use $p_n(x) = \prod_{k=0}^n ((x+k)/k)^{\min(k, n-k)}$, with the standard convention that $0^0 = 1$.

Let $v_p(x)$ denote the maximal value such that $p^{v_p(x)} \mid x$. We have \begin{align*} v_p\left(\prod_{k=0}^n k^{\min(k, n-k)}\right) &= \sum_{k=0}^n \min(k, n-k) v_p(k) \\ &= \sum_{\substack{k=0 \\ p^r \mid k}}^n \min(k, n-k) \end{align*} since $v_p(k) = \#\{r : p^r \mid k\}$. Similarly $$v_p\left(\prod_{k=0}^n (x+k)^{\min(k, n-k)}\right) = \sum_{\substack{k=0 \\ p^r \mid k+x}}^n \min(k, n-k).$$

Hence as @reuns suggests, it suffices to show $$\sum_{\substack{k=0 \\ p^r \mid k+x}}^n \min(k, n-k) \geq \sum_{\substack{k=0 \\ p^r \mid k}}^n \min(k, n-k)\label{*}\tag{*}$$ for all $x \in \mathbb{Z}$.

First consider the contributions to the right-hand side of $\eqref{*}$. These are $k=0p^r, 1p^r, \ldots, Mp^r$ where $Mp^r \leq n < (M+1)p^r$. Say $mp^r \leq n/2 < (m+1)p^r$, so the right-hand side of $\eqref{*}$ is $$0p^r + p^r + \cdots + mp^r + (n-(m+1)p^r) + \cdots + (n-Mp^r).$$

Now consider the left-hand side of $\eqref{*}$. Suppose $x = qp^r \color{red}{-} \delta$ where $0 \leq \delta < p^r$. The terms which contribute are then $k=0p^r+\delta, 1p^r+\delta, \ldots, (M-1)p^r+\delta$, and also $Mp^r+\delta$ if this last is $\leq n$.

We'll match up particular contributions on either side in order to prove $\eqref{*}$. Note that $(m-1)p^r + \delta < mp^r \leq n/2$ and $n/2 < (m+1)p^r \leq (m+1)p^r + \delta$. We begin with

$$ \begin{array}{c|c|c} \text{LHS term} & \text{RHS term} & \text{LHS $-$ RHS contribution} \\ \hline 0p^r+\delta & 0p^r & \delta \\ \vdots & \vdots & \vdots \\ (m-1)p^r+\delta & (m-1)p^r & \delta \\ ? & mp^r & ? \\ mp^r+\delta & ? & ? \\ (m+1)p^r+\delta & (m+1)p^r & -\delta\\ \vdots & \vdots & \vdots \\ (M-1)p^r + \delta & (M-1)p^r & -\delta \\ ? & Mp^r & ? \\ Mp^r+\delta & ? & ? \\ \end{array} $$

The terms without ?'s in all contribute $\delta m - \delta ((M-1)-(m+1)+1) = \delta(2m+1-M)$. Since $2mp^r \leq n < (2m+2)p^r$, it follows that $M \in \{2m, 2m-1\}$, so $2m-M \in \{0, 1\}$. Hence the terms without ?'s contribute either $\delta$ or $2\delta$. We must show the remaining terms cannot overcome this.

If $Mp^r+\delta \leq n$, then the contributions of $Mp^r+\delta$ and $Mp^r$ together give $-\delta$. If $Mp^r+\delta > n$, then $Mp^r+\delta$ does not contribute, but the contribution of $Mp^r$ is $-(n-Mp^r) > -\delta$. In either case, the contribution(s) of $Mp^r$ and perhaps $Mp^r+\delta$ are $\geq -\delta$.

If the contributions of $mp^r+\delta$ and $mp^r$ together are non-negative, then all the contributions together will be $\geq (2m-M+1)\delta-\delta \geq 0$, giving $\eqref{*}$. So, we may suppose the overall contributions of $mp^r+\delta$ and $mp^r$ are negative. This occurs precisely when that contribution is $n-(mp^r+\delta)-mp^r = n-2mp^r-\delta < 0$. As noted above, $n \geq 2mp^r$, so in any case this contribution is $\geq -\delta$. Hence if $2m-M = 1$, then all contributions together give $\geq 2\delta-\delta-\delta \geq 0$.

Hence we are left with the case $M=2m$ and $n-2mp^r-\delta < 0$. In this case, $n < Mp^r+\delta$, and the contributions of $Mp^r, mp^r, mp^r+\delta$ altogether are $-(n-Mp^r) + n-2mp^r-\delta = -\delta$. Hence all contributions together give $\delta-\delta = 0$, completing the proof of $\eqref{*}$.

As a side note, one should never ignore @reuns' comments.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.