# How to prove $\sum\limits_{i =1}^{26} \frac{a_i}{\sum_{j =0}^{i} a_j^2} \leq \sqrt{26}$

Given arbitrary real numbers $a_i$,

Prove that

$$\sum_{i =1}^{26} \frac{a_i}{\sum_{j =0}^{i} a_j^2} \leq \sqrt{26}$$

where $a_0 = 1$

So it will look like:

$$\frac{a_1}{(1+a_{1}^2)} + \frac{a_2}{(1+ a_{1}^2 + a_{2}^2)} + \cdots + \frac{a_{26}}{(1+ a_1^2+ \cdots + a_{26}^2)}$$

-
You are using the same counter in your summation –  Amr Dec 21 '12 at 12:25
Your first sum is not the same as the second. In the first one, the denominator of each term is the sum of squares of 27 terms, whereas in the second, the number of terms in the denominator changes. –  Michael Albanese Dec 21 '12 at 12:29
The second sum is $$\sum_{i=1}^{26} \frac{a_i}{\sum_{j=0}^ia_j^2}$$. –  Michael Albanese Dec 21 '12 at 12:30
Sorry. Fixed it. Thanks for correcting! –  John Chang Dec 21 '12 at 12:31

Here is a proof for the more general inequality $$\sum_{i=1}^n \frac{a_i}{1 + \sum_{j=1}^i a_j^2} \leq \sqrt{n}.$$ where $a_1, \ldots, a_n$ range over $\mathbb{R}$. The method is a little cumbersome so I would be interested in a more direct proof.

I assume this problem comes from a math competition and would be interested to know its source.

Let $S_n$ denote the sum. Clearly we can assume that each $a_i \geq 0$, as otherwise we could increase $S_n$ by swapping the sign of one of the variables. Now make the change of variables $$a_i = t_i \sqrt{1 + a_1^2 + \cdots + a_{i-1}^2}$$ for each $i$ so that $$\frac{a_i}{1 + \sum_{j=1}^{i-1} a_j^2 + a_i^2} = \frac{1}{\sqrt{1 + \sum_{j=1}^{i-1} a_j^2}} \frac{t_i}{1 + t_i^2}$$ and furthermore $$\frac{1}{\sqrt{1 + \sum_{j=1}^{i-1} a_j^2}} = \prod_{j=1}^{i-1} \frac{1}{\sqrt{1 + t_j^2}}.$$ Now we have $$S_n = \sum_{i=1}^n \frac{t_i}{1 + t_i^2} \prod_{j=1}^{i-1} \frac{1}{\sqrt{1 + t_j^2}}.$$ Grouping terms, we get $$S_n = \frac{t_1}{1 + t_1^2} + \frac{1}{\sqrt{1 + t_1^2}} \left( \frac{t_2}{1 + t_2^2} + \frac{1}{\sqrt{1 + t_2^2}} \left( \cdots \right)\right)$$ We therefore define $f : [n] \to \mathbb{R}^+$ inductively by $$f(n) = \max_{t_n \geq 0} \frac{t_n}{1 + t_n^2}$$ and $$f(k) = \max_{t_k \geq 0} \frac{t_k}{1 + t_k^2} + f(k+1) \frac{1}{\sqrt{1 + t_k^2}}.$$ Then we have $S_n \leq f(1)$ (and in fact, $f(1) = \max_{t_1, \ldots, t_n} S_n$).

Note that if $M$ is an upper bound for $f(k+1)$, then $$\max_{t_k \geq 0} \frac{t_k}{1 + t_k^2} + M \frac{1}{\sqrt{1 + t_k^2}}$$ is an upper bound for $f(k)$. It therefore suffices to show that $$f(k) \leq \sqrt{n+1-k}$$ inductively in $k$, starting at $n$.

We have the base case $$f(n) = \max_{t_n \geq 0} \frac{t_n}{1 + t_n^2} \leq \frac{1}{2}.$$ It therefore suffices for us to show $$\frac{t}{1 + t^2} + \sqrt{m} \frac{1}{\sqrt{1 + t^2}} \leq \sqrt{m+1}$$ for every $m \geq 1$ uniformly in $t \geq 0$. With the trivial bound $$\frac{t}{1 + t^2} \leq \frac{t}{\sqrt{1 + t^2}}$$ it suffices to show $$\frac{t + \sqrt{m}}{\sqrt{1 + t^2}} \leq \sqrt{m+1}.$$ Squaring, it suffices to show $$\frac{t^2 + 2 t \sqrt{m} + m}{1 + t^2} \leq m + 1$$ Or, equivalently, $$t^2 + 2 t \sqrt{m} + m \leq m + 1 + (m + 1) t^2$$ or $$2 t \sqrt{m} \leq 1 + m t^2.$$ But this is the AM-GM inequality for the pair $(1, mt^2)$, and the proof is complete.

Note that the method of proof showed that the inequality is not sharp for any $n$.

-
“cumbersome” but natural and relatively straightforward. To see if there is a “more direct” proof, one should compute the optimal maximum, say for $n=3$ (this will be an algebraic number of degree at most $8$). My guess is that in general the maximum is a “generic” algebraic number of degree $2^n$ with no special properties, so that a simpler proof is hopeless. –  Ewan Delanoy Dec 23 '12 at 13:24
@Ewan, I gave up the exact solution when I computed that the $n=2$ case is algebraic of degree $4$. I believe each number is computable only with square roots though. I am not sure this means a simpler proof is totally hopeless, but rather would require the application of $n$ "classical" inequalities which are sharp at different places. I still have no idea how one could do it. –  Pot Dec 23 '12 at 13:30
in general, any inequality involving a polynomial or a rational function can be deduced from finitely many “classical” inequalities by “inducting on the degree”. But would writing out all the constants make us wiser ? –  Ewan Delanoy Dec 23 '12 at 13:35

Suppose that $n$ is a positive integer and that $x\in \mathbb{R}^{n+1}$. By the Cauchy-Schwarz inequality, we have $$\sum_{k=0}^n |x_k| \le \left(\sum_{k=0}^n x^2_k\right)^{1/2} \left(\sum_{k=0}^n 1\right)^{1/2} = \sqrt{n+1}\|x\|$$ Dividing we get $$\sum_{k=0}^n {|x_k|\over {\|x\|^2}} \le {\sqrt{n+1}\over \|x\|}$$ Since the first coordiante of your vector is 1, you have $\|x\|\ge 1$.

From this I am able to obtain $$\sum_{k=0}^n {|x_k|\over {\|x\|^2}} \le \sqrt{n+1}$$

Perhaps you can sharpen this.

-
The sum in the denominator only runs from $j=0$ to $j=i$, not $j=n$. –  Antonio Vargas Dec 21 '12 at 14:57
With some fiddling,I think you can lower this upper bound. –  ncmathsadist Dec 21 '12 at 15:09
Considering that you can get equality in the CS, I highly doubt you can lower the upper bound... The good news is that the LHS is very different than the one in the inequality, so not being able to improve the RHS in this inequality doesn't disprove the original one.... –  N. S. Dec 21 '12 at 18:22