3
$\begingroup$

For a positive integer $n$, define a function $ f_n (x) $ at an interval $ [ 0, n+1 ] $ as $$ f_n (x) = ( \sum_{i=1} ^ {n} | x-i | )^2 - \sum_{i=1} ^{n} (x-i)^2 .$$ Let $ a_n $ be the minimum value of $f_n (x) $. Find the value of $$\sum_{n=1}^{11} (-1)^{n+1} a_n . $$

It is said the answer is 450. I try find the sum $$\sum_{i=1}^{n}(x-i)^2=nx^2-2x\sum_{i=1}^{n}i+\sum_{i=1}^{n}i^2 =nx^2-n(n+1)x+\dfrac{n(n+1))(2n+1)}{6}$$This term looks like a quadratic function,But $(\sum_{i=1}^{n}|x-i|)^2$ seem hard to deal it

$\endgroup$
  • $\begingroup$ The first term is minimized at the median, and the rest becomes trivial is you compare derivatives. $\endgroup$ – LinAlg Apr 19 at 14:10
  • $\begingroup$ @function, I am rather disappointed that you had been offline before your bounty became expired. I wonder if I should I be more prudent next time when your raise a bounty on a question. (This comment will be removed.) $\endgroup$ – Apass.Jack Apr 21 at 15:50
  • $\begingroup$ @user125932 For even $n$, $f_n$ is not convex and its minimum does not occur at $x=\frac{n+1}2$. For example, $f_2(1)=f_2(2)=0<\frac12=f_2(\frac32)$. $\endgroup$ – Apass.Jack Apr 21 at 21:09
  • $\begingroup$ A cursory looks might suggest that $f_n$ is convex and, since it is symmetric about $x=\frac{n+1}2$, its minimum should occur at $x=\frac{n+1}2$. However, $f_n$ is not convex for even $n$ (I did not check for odd $n$). Also, $f_2(1)=f_2(2)=0<\frac12=f_2(\frac32)$. $\endgroup$ – Apass.Jack Apr 28 at 13:53
  • $\begingroup$ @LinAlg It looks like you suggest either it is enough to investigate two terms separately or the whole problem is trivial. While the problem can probably be solved as long as one persists enough, it is not trivial, I believe, in other senses. I would love to see a simple answer from you. $\endgroup$ – Apass.Jack Apr 28 at 14:00
6
+25
$\begingroup$

Let $n$ be some fixed positive integer.

Since $[0,n+1]$ and $f_n(x)$ are symmetric about $x=\frac{n+1}2$, the minimum value of $f_n$ over $[0, n+1]$ is the same as the minimum of $f_n$ over $[0, \frac{n+1}{2}]$. From now on, we will assume $f_n$ is defined on $[0, \frac{n+1}2]$. It is immediate to verify $f_1(x)=0$. From now on, we will assume $n>1$.

As observed in the question, $(\sum_{i=1}^{n}|x-i|)^2$ is not easy to deal with because of the absolute values. The most common way to remove absolute values is, well, to separate the domain of the variable into small pieces so that we know how to take the absolute value in each piece.

Let $\lfloor x\rfloor$ be the integer part of $x$, i.e., $\lfloor x\rfloor\in\mathbb N$ and $0\le x - \lfloor x\rfloor\lt1$. There are two cases for $\lfloor x\rfloor$.

  • $\lfloor x\rfloor=0$. $\quad( \sum_{i=1} ^ {n} | x-i | )^2=( \sum_{i=1} ^ {n} (i-x) )^2=( \frac{n(n+1)}2-nx)^2.$
  • $1\le \lfloor x\rfloor\le \frac{n+1}2$. $\quad( \sum_{i=1} ^ {n} | x-i | )^2=( \sum_{i=1} ^ {\lfloor x\rfloor} (x-i)+\sum_{i=\lfloor x\rfloor+1} ^ {n} (i-x) )^2\\=\left( \sum_{i=1} ^ {\lfloor x\rfloor} x+\sum_{i=\lfloor x\rfloor+1} ^ {n} (-x)+\sum_{i=1} ^ {\lfloor x\rfloor} (-i)+\sum_{i=\lfloor x\rfloor+1} ^ {n}i \right)^2\\=\left( (2\lfloor x\rfloor-n)x-\frac{\lfloor x\rfloor(\lfloor x\rfloor+1)}2+\frac{(n-\lfloor x\rfloor)(n+\lfloor x\rfloor+1)}2\right)^2.$

Note the formula above for the second case holds for the first case, too.

As computed in the question, we have.

$$\sum_{i=1}^{n}(x-i)^2=nx^2-n(n+1)x+\dfrac{n(n+1)(2n+1)}{6}.$$

So, $$\begin{aligned} &\quad\quad f_n(x)=\sum_{i=1} ^ {n}| x-i | )^2 - \sum_{i=1} ^{n} (x-i)^2\\ &=\left( (2\lfloor x\rfloor-n)x-\frac{\lfloor x\rfloor(\lfloor x\rfloor+1)}2+\frac{(n-\lfloor x\rfloor)(n+\lfloor x\rfloor+1)}2\right)^2 - \left(nx^2-n(n+1)x+\dfrac{n(n+1)(2n+1)}{6}\right)\\ &=-nx^2+(n^2+2\lfloor x\rfloor)x+ \text{ (some formula that depends only on } \lfloor x\rfloor\text{ and }n)\\ &=-n\left(x-(\frac n2+\frac{\lfloor x\rfloor}n)\right)^2+ \text{ (some formula that depends only on } \lfloor x\rfloor\text{ and }n).\\ \end{aligned}$$

Since $\left\lfloor\lfloor x\rfloor\right\rfloor=\lfloor x\rfloor$, we have $$f_n(x)-f_n(\lfloor x\rfloor,n)=-n\left(x-(\frac n2+\frac{\lfloor x\rfloor}n)\right)^2+n\left(\lfloor x\rfloor-(\frac n2+\frac{\lfloor x\rfloor}n)\right)^2=n(x-\lfloor x\rfloor)(n+\frac{2\lfloor x\rfloor}n-x-\lfloor x\rfloor). $$

  • If $x\le\frac n2$, we have $n+\frac{2\lfloor x\rfloor}n-x-\lfloor x\rfloor\ge n -x-x\ge0.$
  • Otherwise $x\gt\frac n2.$ Recall that $x\le\frac{n+1}2$.
    • $n$ is even. Then $\lfloor x\rfloor=\frac n2$. We have $n+\frac{2\lfloor x\rfloor}n-x-\lfloor x\rfloor= \frac{n+1}2- x + \frac12\gt0.$
    • $n$ is odd.
      • If $x=\frac {n+1}2$, i.e., $x$ is an integer, $x-\lfloor x\rfloor=0$.
      • Otherwise, suppose $x<\frac {n+1}2$. Then $\lfloor x\rfloor=\frac{n-1}2$, and $n+\frac{2\lfloor x\rfloor}n-x-\lfloor x\rfloor=1-\frac 1n+\frac{n+1}2-x \gt0.$

Combining all cases, we have $f_n(x)-f_n(\lfloor x\rfloor,n)\ge0$. That is, if $f_n(\cdot)$ reaches its minimum at $x$, then it must also reach its minimum at $\lfloor x\rfloor$, an integer.


So, in order to find the minimum of $f_n(x)$, we can restrict $x$ to integers. An easy way to obtain $\sum_{n=1}^{11} (-1)^{n+1} a_n$ should be computing $f_n(x)$ at every possible integer $x$ by brute force, by some programming using your favourite programming language.

Let us check where $f_n(x)$ can reach its minimum. Assume $f_n(x)$ is defined on integers in $[0, \frac{n+1}2]$.

$$\begin{aligned} &\quad\quad f_n(x)\\ &=\left( (2x-n)x-\frac{x(x+1)}2+\frac{(n-x)(n+x+1)}2\right)^2 - \left(nx^2-n(n+1)x+\dfrac{n(n+1)(2n+1)}{6}\right)\\ &=\left(x^2-(n+1)x+ \frac{n^2+n}2\right)^2-\left(nx^2-n(n+1)x+\dfrac{n(n+1)(2n+1)}{6}\right).\\ \end{aligned}$$

Suppose $x+1\le \frac{n+1}2$ so that $f_n(x+1)$ is defined.

$$\begin{aligned} &\quad\quad f_n(x) - f_n(x+1)\\ &=\left( (-(x+x+1)+(n+1))(x^2+(x+1)^2-(n+1)(x+x+1)+n^2+n)\right)+\left(n(x+x+1)-n(n+1)\right)\\ &=(n-2x)(2x^2-2nx+n^2)+(2nx-n^2)\\ &=(n-2x)\left(2(x-\frac n2)^2+\frac {n(n-2)}2\right).\\ &\ge0 \end{aligned}$$

That means, $f_n(0), f_n(1), f_n(2), ...$ is a non-increasing sequence. The last item of the sequence is either $f_n(\frac n2)$ for even $n$ or $f_n(\frac {n+1}2)$ for odd $n$. So,

$$ a_n= \begin{cases} f_n(\frac {n+1}2)\quad \text{ if } n \text{ is odd,}\\ f_n(\frac n2)\quad\quad \text{ if } n \text{ is even.} \end{cases} $$


Now let us compute $a_n$ into closed formula. For odd n, $$\begin{aligned} a_n &=\left((\frac {n+1}2)^2-(n+1)\frac {n+1}2+ \frac{n^2+n}2\right)^2-\left(n(\frac {n+1}2)^2-n(n+1)\frac {n+1}2+\dfrac{n(n+1)(2n+1)}{6}\right)\\ &=\frac{(n^2-1)^2}{16}-\frac{n^3-n}{12}.\\ \end{aligned}$$

So, we have $a_{1}=0$, $a_{3}=2$, $a_{5}=26$, $a_{7}=116$, $a_{9}=340$, $a_{11}=790$.

For even $n$, $$\begin{aligned} a_n &=\left((\frac n2)^2-(n+1)\frac n2+ \frac{n^2+n}2\right)^2-\left(n(\frac n2)^2-n(n+1)\frac n2+\dfrac{n(n+1)(2n+1)}{6}\right)\\ &=\frac{n^4}{16}-\frac{n^3+2n}{12}.\\ \end{aligned}$$ So, we have $a_{2}=0$, $a_{4}=10$, $a_{6}=62$, $a_{8}=212$, $a_{10}=540$.

Finally, we obtain $$\sum_{n=1}^{11} (-1)^{n+1} a_n=0-0 + 2-10 + 26-62 + 116-212 + 340-540 + 790=450.$$

| cite | improve this answer | |
$\endgroup$

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.