Let $a_0<a_1<a_2<\dots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n\ge1$ such that $$a_n<\frac{a_0+a_1+\dots+a_n}{n}\le a_{n+1}$$

This is what I tried:
Let $k\in\mathbb{N}$ and $k\ge1$ such that $a_k<\frac{a_0+a_1+\dots+a_k}k$. Because of $k>0$ we have $$ka_k<a_0+a_1+\dots+a_k$$ Subracting $a_k$ from both sides we get $$(k-1)a_k<a_0+a_1+\dots+a_{k-1}$$ Because of $a_0<a_1<a_2<\dots$ we have that $$a_0+a_1+\dots+a_{k-1}\ge1+2+\dots+k=\frac12k(k+1)$$ Also $$(k-1)a_k\ge(k-1)(k+1)$$ So, we have $$(k-1)(k+1)<\frac12k(k+1)$$ which gives $k<2$. Thus, only solution is $n=k=1$.
But in original solution they proved that $n$ may not be $1$. Where is my mistake?

  • 1
    $\begingroup$ There's an extremely simple, short and elegant solution by Fedor Petrov in the ArtOfProblemSolving forum. $\endgroup$ – user26486 Jan 17 '15 at 13:14
  • $\begingroup$ @mathh. Fedor Petrov said that $b_n<a_0\le b_{n+1}$. Why it means that there are exact one $n$ such that $b_n<a_0\le b_{n+1}$ is true? $\endgroup$ – user164524 Jan 17 '15 at 13:32
  • $\begingroup$ $(b_i)_{i\in\mathbb N_0}$ is increasing, so all the intervals $(b_i;b_{i+1}], i\in\mathbb N_0$ contain at least one element and the union of all these intervals (they all are disjoint) is $\mathbb N_0$, so there is at least one interval that contains $a_0$. Also, there can't be two or more such intervals, since all the intervals are disjoint. $\endgroup$ – user26486 Jan 17 '15 at 13:35
  • $\begingroup$ @mathh. But, we defined $b_n$ as $b_n=(a_n-a_{n-1})+\dots+(a_n-a_1)$, so main inequality will be $b_n+a_n<a_0\le b_{n+1}$ instead of $b_n<a_0\le b_{n+1}$, right? $\endgroup$ – user164524 Jan 17 '15 at 13:45
  • $\begingroup$ The main inequality is $(n-1)a_n-a_{n-1}-a_{n-2}-\cdots-a_1<a_0\iff (a_n-a_{n-1})+(a_n-a_{n-2})+\cdots+(a_n-a_1)=b_n<a_0$. $\endgroup$ – user26486 Jan 17 '15 at 13:49

You have that $$a_0+a_1+\cdots+a_{k-1}>(k-1)a_k\\a_0+a_1+\cdots+a_{k-1}\geq\frac{1}{2}k(k+1)$$ This doesn't imply that $$\frac{1}{2}k(k+1)>(k-1)a_k\geq(k-1)(k+1)$$


Your Answer

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