# Simple sum inequality proof

Consider the following sequences of length $n$. We are given $\sum_{i=1}^{n} c_i = \omega(n^{3/2})$ and $\sum_{i=1}^{n} d_i = \omega(n^{3/2})$ where each $c_i$ and $d_i$ is greater than 1 and at most $n$. The omega notation is to say that the sums are strictly greater than $O(n^{3/2})$ asymptotically, i.e, both the sums are $O(n^{3/2 + \epsilon})$ for some small $\epsilon > 0$.

I wish to prove that the inner product of the two sequences $\sum_{i=1}^{n} c_i d_i = \omega(n^2)$. Note that if all $c_i = d_i = \sqrt{n}$, then $\sum_{i=1}^{n} c_i d_i = O(n^2)$. I feel there is some straightforward reverse cauchy schwarz inequality that should show this. I am aware of Polya-Szego’s inequality but it gives a weaker bound.

## 1 Answer

If $$c_i = \left\{ \begin{array}{lr} 1 & : i \text{ even}\\ i^{\frac{1}{2}+\epsilon} & : i \text{ odd} \end{array} \right.$$ and $$d_i = \left\{ \begin{array}{lr} 1 & : i \text{ odd}\\ i^{\frac{1}{2}+\epsilon} & : i \text{ even} \end{array} \right.$$

Then $\sum_{i=1}^n c_i$, $\sum_{i=1}^n d_i$ are on the order of $n^{3/2+\epsilon}$, but so is $\sum_{i=1}^n c_id_i$.