Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

For positive integers $n\ge c\ge 5$, why does $$c+2(n-c)+\frac{(n-c)^2}{4}\le\frac{(n-1)^2}{4}+1\text{ ?}$$

share|cite|improve this question
This inequality is wrong. – Did Jun 18 '12 at 18:35
It comes from the third page of the paper (the link looks currently down though) – Fred Jun 18 '12 at 18:42
...Where I am sure the additional condition $c\geqslant5$ is not omitted--unlike in the first version of the question here. – Did Jun 18 '12 at 19:35
@did Yes, sorry, the original post contained this mistake. – Fred Jun 25 '12 at 14:56
up vote 2 down vote accepted

To avoid fractions, we multiply the left-hand side by $4$, obtaining $$(n-c)^2+8(n-c)+4c.$$ Complete the square. We get $$(n-c+4)^2 +4c -16.$$ Now calculate $[(n-1)^2 +4]-[(n-c+4)^2 +4c -16]$. The difference of squares factors as $(c-5)(2n-c+3)$, so $$\begin{align}[(n-1)^2 +4]-[(n-c+4)^2 +4c -16]&=(c-5)(2n-c+3)-4(c-5)\\ &=(c-5)(2n-c-1).\end{align}$$ The condition $c \ge 5$ ensures that $c-5\ge 0$. And since $n \ge c$, the term $2n-c-1$ is positive.

share|cite|improve this answer
But the last assertion of your answer is wrong: we have $c\ge 5$, not $c\le 5$. – Fred Jun 25 '12 at 14:43
@Fred: Thank you. I had a typo on the last line. The condition $c\ge 5$ makes $4c-16\ge 4$. Which is what we want. – André Nicolas Jun 25 '12 at 14:52
But we need to show that $((n-c)+4)^2+4c-16\le (n+1)^2+4$, so $4c-16\ge 4$ is the wrong direction, no ? – Fred Jun 25 '12 at 14:53
Thanks for your help! – Fred Jun 25 '12 at 15:54
@Fred: The thanks go the other way, you helped fix an error. – André Nicolas Jun 25 '12 at 16:00

Essentially, you want to prove that (multiplying throughout by $4$) $$c^2 -2cn -4c +n^2 + 8n \leq n^2 -2n +5$$ i.e. $$c^2 - 2cn -4c + 10n \leq 5$$ Since $n \geq c \geq 5$, we have that $(10-2c)n \leq (10-2c)c$ (since $10-2c \leq 0$). Hence, $$c^2 -4c + (10-2c)n \leq c^2 - 4c +(10-2c)c = -c^2 + 6c = c(6-c) = 9 - (c-3)^2$$ Note that the function is a decreasing function for $c \geq 3$. Hence, it is a decreasing function for $c \geq 5$ as well. Hence, the maximum occurs at $c=5$, which gives us that $c(6-c) \leq 5 (6-5) = 5$, which is what we wanted.

Putting these together, we get that $$c+2(n-c)+\frac{(n-c)^2}{4}\le\frac{(n-1)^2}{4}+1$$

share|cite|improve this answer
Alternatively,$$(n-c)^2\leq (n-5)^2 \leq (n-5)^2 + (4c-20)$$ Multiplying out and subtracting gives your $c^2-2cn-4c+10n\leq 5$ as you've already shown is required. – Thomas Andrews Jun 18 '12 at 18:56

If you expand the two sides, you will get

\begin{equation} \frac{c^2}{4}-\frac{cn}{2}-c+\frac{n^2}{4}+2n\leq\frac{n^2}{4}-\frac{n}{2}+\frac{5}{4} \end{equation}

\begin{equation} \frac{c^2}{4}-\frac{5}{4}-c\leq n\frac{c-5}{2} \end{equation}

If c=5 than the inequality is satisfied, assuming $5\leq c$ we have

\begin{equation} \frac{c-5}{2} -\frac{2c}{c-5}\leq n \end{equation}

I think you can use induction to prove this inequality.

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.