, 2010

(By Gabriel Carroll). Multiplying together the inequalities $a_{2i-1}a_{2i} \le 4i - 1$ for $i = 1, 2, \dots, 1005$, we get
$$a_1 a_2 \cdots a_{2010} \le 3 \cdot 7 \cdot 11 \cdots 4019. \qquad (1)$$
It remains to show that this bound can be attained.
Let
$$a_{2008} = \sqrt{\frac{4017 \cdot 4018}{4019}}, \quad a_{2009} = \sqrt{\frac{4019 \cdot 4017}{4018}}, \quad a_{2010} = \sqrt{\frac{4018 \cdot 4019}{4017}},$$
and define $a_i$ for $i < 2008$ by downward induction using the recursion
$$a_i = (2i + 1)/a_{i+1}.$$
We then have
$$a_i a_j = i + j \quad \text{whenever } j = i + 1 \text{ or } (i, j) = (2008, 2010). \qquad (2)$$
We will show that (2) implies $a_ia_j \le i+j$ for all $i < j$, so that this sequence satisfies the hypotheses of the problem. Since $a_{2i-1}a_{2i} = 4i-1$ for $i = 1, \dots, 1005$, the inequality (1) is an equality, so the bound is attained.
We show that $a_ia_j \le i+j$ for $i < j$ by downward induction on $i+j$. There are several cases:

* If $j = i + 1$, or $(i,j) = (2008, 2010)$, then $a_ia_j = i + j$, from (2).

* If $(i,j) = (2007, 2009)$, then
$$a_i a_{i+2} = \frac{(a_i a_{i+1})(a_{i+2} a_{i+3})}{(a_{i+1} a_{i+3})} = \frac{(2i+1)(2i+5)}{2i+4} < 2i+2.$$
Here the second equality comes from (2), and the inequality is checked by multiplying out:
$$(2i+1)(2i+5) = 4i^2 + 12i + 5 < 4i^2 + 12i + 8 = (2i+2)(2i+4).$$

* If $i < 2007$ and $j = i + 2$, then we have
$$a_i a_{i+2} = \frac{(a_i a_{i+1})(a_{i+2} a_{i+3})(a_{i+2} a_{i+4})}{(a_{i+1} a_{i+2})(a_{i+3} a_{i+4})} \le \frac{(2i+1)(2i+5)(2i+6)}{(2i+3)(2i+7)} < 2i+2.$$
The first inequality holds by applying the induction hypothesis for $(i+2, i+4)$ and applying (2) for the other pairs. The second inequality can again be checked by multiplying out: $(2i+1)(2i+5)(2i+6) = 8i^3 + 48i^2 + 82i + 30 < 8i^3 + 48i^2 + 82i + 42 = (2i+2)(2i+3)(2i+7)$.

* If $j - i > 2$, then
$$a_i a_j = \frac{(a_i a_{i+1})(a_{i+2} a_j)}{a_{i+1} a_{i+2}} \le \frac{(2i+1)(i+2+j)}{2i+3} < i+j.$$
Here we have used the induction hypothesis for $(i+2, j)$, and again we check the last inequality by multiplying out: $(2i+1)(i+2+j) = 2i^2+5i+2+2ij+j < 2i^2+3i+2ij+3j = (2i+3)(i+j)$.

This covers all the cases and shows that $a_ia_j \le i+j$ for all $i < j$, as required.