AoPS Academy
index this yr (118.5 on amc10+ 9 on AIME) i’m in 7th rn btw first year comp math also. I will grind so hard until like 30 hrs/week. I’m ok at proofs. made mc nats
+1 w
, which is true. The base case 
gives 
. Let 
and 
. Therefore, ![$b=\frac{1}{4}*[(\sum_{i=0}^{n+1}{a_i})^2-\sum_{i=0}^{n+1}{a_i}-(\sum_{i=0}^{n}{a_i})^2+\sum_{i=0}^{n}{a_i}]=\frac{1}{4}[a_{n+1}*(2\sum_{i=0}^{n}{a_i}+a_{n+1})-a_{n+1}]=\frac{a_{n+1}}{2}[\frac{2\sum_{i=0}^{n}{a_i}+a_{n+1}-1}{2}]=\frac{a_{n+1}}{2}[\sum_{i=0}^{n}{a_i}+(\frac{a_{n+1}-1}{2})]$](http://latex.artofproblemsolving.com/7/c/e/7ce63357487ed02032f83131a48b6f2643a7ec93.png)
. Note that ![$a=\frac{a_{n+1}}{2}[(n+1)(a_{n+1}-1)]$](http://latex.artofproblemsolving.com/e/a/f/eaf8b279580b810f23ba6c7df45df7b434d4a980.png)
. Since 
. Then 
for 
with the equality case when 
for all 
.
as a base case proves the desired statement for all nonnegative integers 
which is stronger than for all positive integers 
At least pointing out that you are proving a stronger statement should not get docks, but should be no docks regardless.
when its actually 
Let 
and introduce a new term 
We have that 
and since 
is nonnegative we have
and since is nonnegative we have
Then, we have
Then, divide by 
and add the inequality from the inductive hypothesis, and we have the desired result.
is there an 
case when the induction looks like this or nah
rooms, with the th room having 
people. Number the people in each room 
Then 
calculates the number of ways to choose two people from the same room 
and then picking one of them to move either 
rooms down. Then, if the number of the person who went down is 
we find the person in the new room he went to with the same number 
So the end result is this matched person and the person from the intial room who did not move. It is clear that each end result from the process is unique.
counts the number of ways to choose 
people from the entire group of people directly. Since the above is an injective map the desired result follows. QED
(which we permit) there is nothing to prove. Hence to prove by induction on , it would be sufficient to verify ![\[ 2n \binom{a_n}{2} \le \binom{a_0 + a_1 + \dots + a_n}{2} - \binom{a_0 + a_1 + \dots + a_{n-1}}{2}. \]](http://latex.artofproblemsolving.com/f/0/6/f06a1f32893b335ec9495fc70e161a02716d9f1e.png)
Rearranging the terms around, that's equivalent to proving 
However, the last line is obvious because 
, and 
.
and 
for 
.
![\[ \sum_{i = 0}^n i \binom{a_i}{2} \le \dfrac{\sum_{i = 0}^n i}{(n + 1)^2} \sum_{i = 0}^n \binom{a_i}{2} = \dfrac{n}{2(n + 1)} \sum_{i = 0} \binom{a_i}{2} \le \dfrac{1}{2} \sum_{i = 0}^n \binom{a_i}{2} \le \dfrac{1}{2} \binom{ \sum_{i = 0}^n a_i }{2}\]](http://latex.artofproblemsolving.com/a/5/d/a5d9a1e9ee714c88e4fefc01b02666bac24bb87b.png)
YUH.
so the inequality becomes ![\[ \sum_{i=0}^n 2ia_i(a_i - 1) \le \left( \sum a_i \right)^2 - \sum a_i. \]](http://latex.artofproblemsolving.com/5/2/f/52f3ca3706e6b9bfd83811f052d7815ac6a9e3af.png)
Now notice that ![\[ a_ia_j \ge a_j^2 \]](http://latex.artofproblemsolving.com/e/8/a/e8abf3ee9377c2cebf58a42a045deec359bb0eaf.png)
for 
. In particular, on the left hand side the coefficient of 
is 
, and on the right hand side, the sum of the coefficients of the 
terms where 
is precisely , so we can remove all the squared terms with the cross terms on the right, requiring us to prove ![\[ \sum_{i = 0}^n -ia_i \le \sum a_i^2 - a_i. \]](http://latex.artofproblemsolving.com/a/5/6/a5668c227a06ec4600cdab63c2895bfe5c762325.png)
![\[ \ln \left( \frac{27abc}{(a+b+c)^3} \right) \le \frac{(a-b)^2+(b-c)^2+(c-a)^2}{3}. \]](http://latex.artofproblemsolving.com/d/e/2/de244e2a3c44720d4f7b27b216af6b3971aad8b2.png)
One wonders: How does one possibly solve this inequality??!?!?!?!? It is simple, dear friend. Notice that ![\[ \ln \left( \frac{27abc}{(a+b+c)^3} \right) \le 0 \le \frac{(a-b)^2+(b-c)^2+(c-a)^2}{3}. \]](http://latex.artofproblemsolving.com/2/7/e/27e4982e412a393bfdc77ad2d21385fddc99073e.png)
![\[ \sum_{i = 0}^n -ia_i \le 0 \le \sum a_i^2 - a_i. \]](http://latex.artofproblemsolving.com/b/c/7/bc77864bb989345a5acdb16656fea1e465d354f3.png)
Through the miracle work of CMJ 1226 we are done.
be nonnegative integers such that 
Prove that![\[
\sum_{i=0}^n i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_n}{2}.
\]](http://latex.artofproblemsolving.com/c/4/9/c49d0ccfef69402d05dc44d721172498c605cf7e.png)
Note: 
for all nonnegative integers 
.
or 
.
balls split into 
Then, after multiplying both sides by 
-
different pairs of balls, so the inequality holds. I barely finished this writeup before time ended but I hope it gets full points.
works
right?
Equality holds when 
and 
.
for all nonnegative integers 
of nonnegative integers satisfying 
for some 
where 
Then, it follows that if we have some 
of non-negative integers satisfying 
then we will have 
It suffices to show that the desired inequality will then hold for the 
-
for any nonnegative integer 
satisfying 
It is easy to show that 
is nonnegative for all nonnegative integers 
and we also know that 
because all of 
are nonnegative. Therefore, it suffices to prove that 
This easily follows from the fact that 
for all 
concluding the inductive step.
and also 
,
condition properly.
which is already more than what we needed thus we are done, equality holds when 
.