Upper bound on $n$ in terms of $\sum_{i=1}^na_i$ and $\sum_{i=1}^na_i^2$, for $a_i\in\mathbb{Z}_{\ge 1}$.

Question

Assume that we have some positive integers $a_1,\ldots,a_n$, only we don't know how many. All we know is the value of $\sum_{i=1}^na_i$ and $\sum_{i=1}^na_i^2$. Then QM-AM gives $$n\ge\frac{\left(\sum_{i=1}^na_i\right)^2}{\sum_{i=1}^na_i^2}.$$ In fact, this bound is tight; we have equality if all the $a_i$ are equal. Can we find a good upper bound on $n$ as well?

Answer 1

Fix $n$ and $\sum_{i=1}^na_i$ and assume $\sum_{i=1}^na_i^2$ to be maximal. WLOG, assume the sequence is increasing.

Suppose there is an $1\le i< n$ with $a_i>1$. The sequence $a_1,\ldots,a_{i-1},a_i-1,a_{i+1},\ldots,a_n+1$ has the same length and sum as $a_1,\ldots,a_i$, but $$(a_i-1)^2+(a_n+1)^2>a_i^2+a_n^2,$$ which contradicts the maximality of $\sum_{i=1}^na_i^2$. Therefore, $a_1=\dots=a_{n-1}=1$ and $$\sum_{i=1}^nb_i^2\le(n-1)+\left(\sum_{i=1}^nb_i-(n-1)\right)^2$$ for all sequences $b_1,\ldots,b_n$ of positive integers. This can be rewritten as $$(n-1)^2+\left(1-2\sum_{i=1}^nb_i\right)(n-1)+\left(\sum_{i=1}^nb_i\right)^2-\sum_{i=1}^nb_i^2\ge 0$$ The LHS is quadratic in $n-1$ with roots $$-\frac12+\sum_{i=1}^nb_i\pm\frac12\sqrt{1-4\sum_{i=1}^nb_i+4\sum_{i=1}^nb_i^2}$$ Note that $$n\ge \frac12+\sum_{i=1}^nb_i+\frac12\sqrt{1-4\sum_{i=1}^nb_i+4\sum_{i=1}^nb_i^2}>\sum_{i=1}^nb_i,$$ is impossible, so we conclude that $$n\le \frac12+\sum_{i=1}^nb_i-\frac12\sqrt{1-4\sum_{i=1}^nb_i+4\sum_{i=1}^nb_i^2}.$$

Answer 2

Let do this: $$\forall_i: 1 \leqslant a_i \Longrightarrow (a_i+1) \leqslant (2a_i) \Longrightarrow (a_i+1)^2 \leqslant (2a_i)^2 \Longrightarrow \sum_{i=1}^n (a_i+1)^2 \leqslant \sum_{i=1}^n (2a_i)^2 \Longrightarrow$$ $$\Longrightarrow \sum_{i=1}^n (a_i^2+2a_i+1) \leqslant \sum_{i=1}^n (4a_i^2) \Longrightarrow \sum_{i=1}^n (a_i^2)+ \sum_{i=1}^n (2a_i)+ \sum_{i=1}^n (1) \leqslant 4\sum_{i=1}^n (a_i^2) \Longrightarrow$$ $$\Longrightarrow n \leqslant 3\sum_{i=1}^n (a_i^2) -2\sum_{i=1}^n (a_i)$$ I hope you like this.