MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Question : Is the following true for any $n,N\in\mathbb N$?

$$\sum_{k_1+k_2+\cdots+k_N=n,\ k_i\ge0\in\mathbb Z}\frac1{\prod_{j=1}^{N}\{(N-1)k_j+1\}}\le 1$$

Motivation : I've known the $N=3$ case :

$$\sum_{k_1+k_2+k_3=n,\ k_i\ge0\in\mathbb Z}\frac1{(2k_1+1)(2k_2+1)(2k_3+1)}\le 1$$

I proved this inequality by estimating the left hand side with integral. After proving this, I reached the above expectation by using computer. The above expectation seems true, but I'm facing difficulty. I would like to know how to prove this (if it's true) and any relevant references.

Remark : This question has been asked previously on math.SE without receiving any answers.

Update : I'm going to show the proof for $N=3$ case without using integral. This is because it seems that this idea can be generalized (though I'm facing difficulty).

For any non-negative integer $n$, $$\sum_{k_1+k_2+k_3=n,\ k_i\ge0\in\mathbb Z}\frac1{(2k_1+1)(2k_2+1)(2k_3+1)}\le 1$$

Proof : Let $A_n$ be the left hand side, and suppose that $\sum$ represents $\sum_{k_1+k_2+k_3=n,k_i\ge 0\in\mathbb Z}$. Noting that $(2k_1+1)+(2k_2+1)+(2k_3+1)=2n+3$, we get $$\begin{align}A_n & =\sum\frac{(2k_1+1)+(2k_2+1)+(2k_3+1)}{(2n+3)(2k_1+1)(2k_2+1)(2k_3+1)}\\ & =\frac{1}{2n+3}\sum\left\{\frac{1}{(2k_1+1)(2k_2+1)}+\frac{1}{(2k_2+1)(2k_3+1)}+\frac{1}{(2k_3+1)(2k_1+1)}\right\}\\ & =\frac{3}{2n+3}\sum\frac{1}{(2k_1+1)(2k_2+1)}\\ & =\frac{3}{2n+3}\sum_{j=0}^n\sum_{k_1+k_2=j,k_i\ge 0\in\mathbb Z}\frac{1}{(2k_1+1)(2k_2+1)}\\ & \le \frac{3}{2n+3}\left(1+\frac 23 n\right)=1\end{align}$$ Here, I used $$B_0=1, B_j\le \frac 23\ (j=1,2,\cdots,n)$$ where $$B_j=\sum_{k_1+k_2=j,k_i\ge 0\in\mathbb Z}\frac{1}{(2k_1+1)(2k_2+1)}.$$

share|cite|improve this question
Dear @mathlove: Could you please try to add a top level tag to this question? Thank you. – Ricardo Andrade Oct 19 '13 at 10:34
@RicardoAndrade: Well, I know neither what the top level tag is nor how to add it. – mathlove Oct 19 '13 at 15:31
The top level tags are tags like 'nt.number-theory' and 'at.algebraic-topology' which start with a two letter code. They roughly follow their arxiv counterparts. These tags can be added like any other tag, such as the tag 'inequalities' already present in this question. You only have to edit the question and add another tag. I hope that helps. – Ricardo Andrade Oct 19 '13 at 15:49
@Ricardo, I thought of those same two tags, but I'm not sure either one is appropriate. I have also tried, without any success, to find a full listing of two-letter-code tags in use here. – Gerry Myerson Oct 20 '13 at 10:14
@Ricardo, yes, but it would be nice (in my opinion) if there were a list of arXiv tags readily available on this website. – Gerry Myerson Oct 20 '13 at 11:27

This is not an answer, but I want to use displays. What you are asking is whether the coefficients of the taylor expansion of $$\left( \sum_{k=0}^\infty \frac{x^k}{(N-1)k+1} \right)^N$$ are all at most 1. Unfortunately the summation is a hypergeometric function that doesn't have a general simplification. You can easily prove the conjecture for small $n$ and all $N$, or for small $N$ and all $n$ by expanding it. In general you might be able to bound it with a contour integral or something like that. I believe it is true.

share|cite|improve this answer
Actually, after this is said, you should have extremely strong willpower to suppress the natural desire to recall that the function with all coefficients $1$ is $\frac 1{1-z}$ and to raise both sides to the power $\frac 1N$, i.e., to try to check if the coefficients of $(1-z)^{-1/N}$ are at least $\frac 1{(N-1)k+1}$. :-) – fedja Oct 28 '13 at 23:16

This should be a comment rather than an answer, since I only have plausible strategies to suggest. But I'm new here and don't have enough reputation to leave comments.

Plausible Strategy #1: As Brendan says, your sums are coefficients in the Taylor expansion of $$S_N(x) = \left( \sum_{k=0}^\infty \frac{x^k}{(N-1)k+1} \right)^N.$$ I computed some expansions of these series and it looks like, perhaps, the coefficient of $x^n$ ($n\ge 2$) increases monotonically w.r.t. $N$. You could try to prove this and also prove that the limit of each coefficient as $N\to\infty$ is 1. I think I can show that $S_N(x)$ approaches $\dfrac 1{1-x}$ pointwise for $x\in (-1,1)$, which, though not sufficient for what you want to do, is at least encouraging.

Plausible Strategy #2: If we group like terms in your unit fraction sum, we can express it as a sum indexed over partitions of $n$. I'm too lazy to type the general formula but here it is for $n=3$, which ought to be suggestive enough: $$\left(\frac{N(N-1)(N-2)}{3!}\cdot\frac 1{N^3}\right) + \left(\frac{N(N-1)}{1!1!}\cdot\frac 1{(2N-1)\cdot N}\right) + \left(\frac{N}{1!}\cdot\frac 1{3N-2}\right)$$ Here the terms correspond to $\pi=(1,1,1),(2,1),(3)$ respectively. The coefficients are just garden-variety multinomial coefficients. Now if we consider the terms corresponding to partitions with $r\ge 3$ parts, their numerators are $< (N-1)^r$ and their denominators are $> k(N-1)^r$, where $k$ is the leading coefficient. So, all of these terms undershoot their limits as $N\to\infty$.

When $n$ is large, almost all partitions of $n$ have 3 or more parts, so (a) your conjecture seems likely to be true and (b) you may be able to prove it by bounding a relatively small and simple subset of the terms.

share|cite|improve this answer
up vote 1 down vote accepted

I'm posting an answer just to inform that the question has received an answer by Ivan Loh on MSE.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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