prove that $a_1 + \cdots +a_n \le n^2. $ Let $n$ be a positive integer, and consider a sequence $a_1 , a_2 , \cdots , a_n $ of positive integers. Extend it periodically to an infinite sequence $a_1 , a_2 , \cdots $ by defining $a_{n+i} = a_i $ for all $i \ge 1$. If $a_1 \le a_2 \le \cdots \le a_n \le a_1 +n $  and $a_{a_i } \le n+i-1 \quad\text{for}\quad i=1,2,\cdots, n, $ prove that $a_1 + \cdots +a_n \le n^2. $
Any help? I tried and noticed that for all $i \le a_1$, we have $a_i \le n$. Then for all $i \in \{2, 3, \cdots, a_1\},$ we have $a_{a_i} \le n+i-1$.
 A: This is a great question to showcase how you can interpret that statement. I suggest that you try to make sense of the condition, and understand how it restricts the values.
The main observation that you need is: If $a_i = k$, then $a_k \leq n+i - 1$ and thus

 In particular, if $ a_j \geq n+i$, then $j > k$.


Let $a_1 = I$.
Show that $I \leq n$. (Why?)
Let $K$ be the largest index from 1 to $n$ such that $a_k \leq n$.
If this doesn't exist, then  $\sum a_i \leq n^2$ and we are done.      So let's assume that it exists.
Since $ a_I = a_{a_1}  \leq  n, $ so $ K \geq I$.
Let $\delta _i$ count the number of values of $a_i$ that are $ \geq n+i$.
The above observation (in hidden text) states that $ \delta_i \leq (n-a_i)$.
The condition $a_n \leq n+I$ tells us that $ \delta_i = 0 $ for $ i > I$.
We split the summation into 2 parts:

*

*$ \sum_{i \leq K} a_i = \sum_{i\leq K} n - (n-a_i) =  nK - \sum_{i\leq I} (n-a_i).$

*$\sum_{i > k } a_i  = \sum_{i>k} \sum_{j=1}^{a_i} 1 = n(n-K) + \sum_{i\leq I} \delta_i $ by changing the order of summation.

Show that $ \sum_{i \leq I } \delta_i =  \sum_{i \leq K } \delta_i$. (Why?)
Hence, $ \sum a_i = [nK - \sum_{i\leq K} (n-a_i)] + [n(n-K) + \sum_{i \leq I} \delta_i] = n^2 + \sum_{i\leq K } \delta_i - (n-a_i ) \leq n^2. $
Notes:

*

*There is a very nice pictorial representation of this idea. For a valid sequence, plot the values $ (i, a_i)$ on a grid square. Then, the values are non-decreasing. The left triangle of squares representing the "undercount" arising from $a_i \leq n$, can be rotated and flipped to more than cover the right triangle of squares representing the "over count" arising from $a_i  > n$.

A: Notice that in the range $a_1$ to $a_1+n$ there are $(a_1+n)-(a_1)+1=n+1$ positive integers
Hence from the inequality $a_1\leq a_2 \leq a_3 \leq ... \leq a_n \leq a_1+n$ we can directly conclude that $a_i=a_1+i-1$ for all $1<i\leq n$ and $a_1$ can be any positive integer. Hence we get
$$a_1+a_2+...+a_n=a_1+(a_1+1)+(a_1+2)+...+(a_1+n-1)=na_1+\frac{n(n-1)}{2}$$
Now we are left to show that $a_1+\frac{n-1}{2}\leq n$. Which is true as
$$a_1+\frac{n-1}{2}\leq n$$
$$\frac{n-1}{2}\leq n-a_1\leq n-1$$
Which is definitely true. Hence proved!
