Integer Sequence with a Restriction

At first glance, plugging in $j=500$ and $i=1000$ gives $a_{500} > 1007$ , so the answer should be $1008$ . But there is a tighter bound; this is because the sequence is of integers , not real numbers.

First, we compare $a_{1000}$ to $a_{999}$ . We see that using the condition, $a_{999} > \dfrac{999}{1000}\cdot 2014\approx 2011.9$ so $a_{999} \ge 2012$ Comparing $a_{998}$ with $a_{999}$ , we obtain (skipping calculations) $a_{998} \ge 2010$

Comparing $a_{998}$ with $a_{997}$ , we obtain $a_{997}\ge 2008$

It appears that this pattern continues, so we conjecture that for all $k$ , the sequence satisfies $a_k \ge 14+2k$

Now let's try to prove it using induction. We first check the base case: does $a_{1000}\ge 14+2(1000)$ ? Yes it does.

Now we assume $a_k \ge 14+2k$ and try to prove that $a_{k-1} \ge 12+2k$ .

Plugging in $i=k$ and $j=k-1$ , we see that $ka_{k-1} > (k-1)a_k$

Rearranging: $a_{k-1} > \dfrac{k-1}{k}\cdot a_k$

Using the fact that $a_k \ge 14+2k$ :

$a_{k-1} > \dfrac{(k-1)(14+2k)}{k}$

Now to prove that $a_{k-1}\ge 12+2k$ , we must prove that $12+2k > \dfrac{(k-1)(14+2k)}{k} > 11+2k$

Multiply $k$ on all sides of the inequalities:

$k(12+2k) > (k-1)(14+2k) > k(11+2k)$

Expanding: $2k^2+12k > 2k^2+12k-14 > 2k^2+11k$

Clearly, $2k^2+12k > 2k^2+12k-14$ for al $k$ . However, when does $2k^2+12k-14 > 2k^2+11k$ ?

Simplifying, we see that we must have $k > 14$ . However, this is not a problem since we just want to go down to $k=500$ .

Since we have proved that $a_k \ge 14+2k$ for all $k > 14$ , we can just plug in $k=500$ to obtain $a_{500}\ge \boxed{1014}$ and we are done.