if $a_n=\frac{a_{[\frac{n}{2}]}}{2}+\frac{a_{[\frac{n}{3}]}}{3}+\ldots+\frac{a_{[\frac{n}{n}]}}{n}$,then $a_{2n}<2a_{n}$ Question:

Consider the following sequence : $$a_1=1 ; a_n=\frac{a_{[\frac{n}{2}]}}{2}+\frac{a_{[\frac{n}{3}]}}{3}+\ldots+\frac{a_{[\frac{n}{n}]}}{n}$$. Prove that: $$a_{2n}< 2a_{n } (\forall n\in\mathbb{N})$$

where $[x]$ is the largest integer not greater than x
This problem is Kazakhstan NMO 2013 problem:see:link
first I want use Mathematical induction solve this problem.
since
$n=1$,then $a_{2}=\dfrac{1}{2}$.so
$$a_{2}=\dfrac{1}{2}<1=2a_{1}$$
Assume that $n$ have
$$a_{2n}<2a_{n}$$
then
$$a_{2n+2}=\dfrac{a_{n+1}}{2}+\dfrac{a_{[(n+1)/3]}}{3}+\cdots+\dfrac{a_{1}}{n+1}$$
then I can't.Thank you 
 A: First let's prove that $(a_n)$ is increasing for $n \geq 2$. We have $a_1=1,a_2=0.5, a_3=1/2+1/3$ so $a_3\geq a_2$. We have
$$ a_{n+1}-a_n = \sum_{k=2}^n \frac{a_{[(n+1)/k]}-a_{[n/k]}}{k}+1/(n+1).$$
Suppose that for every $2\leq i,j \leq n$ with $i<j$ we have $a_i\leq a_j$. Therefore in the above sum the only way that the term $a_{[(n+1)/k]}-a_{[n/k]}$ could be negative is to have $[(n+1)/k]=2$ and $[n/k]=1$ for some $k$. This happens precisely if $n < 2k\leq n+1$. Therefore, if $n+1$ is odd the sum is positive and $a_{n+1}>a_n$. If $n+1=2k$ is even we have
$$ a_{n+1}-a_n \geq \frac{1/2-1}{k}+\frac{1}{n+1} =-\frac{1}{2k}+\frac{1}{2k}=0 .$$
By induction $(a_n)$ is increasing for $n \geq 2$.
We have
$$ a_{2n} = \frac{a_n}{2}+\sum_{k=2}^n \frac{a_{[2n/(2k)]}}{2k}+\sum_{k=1}^{n-1}\frac{a_{[2n/(2k+1)]}}{2k+1}=$$
$$a_n+\sum_{k=1}^{n-1}\frac{a_{[2n/(2k+1)]}}{2k+1}\ \ \  (*)$$
When we look at $\sum_{k=1}^{n-1}\frac{a_{[2n/(2k+1)]}}{2k+1}$ we want to use the fact that $[2n/(2k+1)] \leq [2n/(2k)]$ and then use the monotonicity inequality proved above. We need to be careful in the case where $[2n/(2k+1)]=1$ and $[2n/(2k)]=2$, since then the monotonicity does not hold. If the last two equalities hold then 
$$ 4k \leq 2n < 4k+2 $$
so we may have problems only when $n=2k$ is even. If $n$ is odd then 
$$\sum_{k=1}^{n-1}\frac{a_{[2n/(2k+1)]}}{2k+1} \leq \sum_{k=1}^{n-1} \frac{a_{[n/k]}}{2k}=\frac{a_n}{2}+\sum_{k=2}^{n-1}\frac{a_{[n/k]}}{2k}=a_n -\frac{1}{2n}<a_n.$$
If $n=2p$ is even then we may apply the monotonicity inequality only for $k \neq p$ so
$$\sum_{k=1}^{n-1}\frac{a_{[2n/(2k+1)]}}{2k+1} \leq \sum_{k=1, k \neq p}^{n-1} \frac{a_{[n/k]}}{2k}+\frac{1}{2p+1}=$$ $$=\frac{a_n}{2}+\sum_{k=2}^{n-1} \frac{a_{[n/k]}}{2k}+\frac{1}{n+1}-\frac{0.5}{2p}=$$
$$=\frac{a_n}{2}+\frac{a_n}{2}-\frac{1}{2n}+\frac{1}{n+1}-\frac{1}{2n}=a_n+\frac{1}{n+1}-\frac{1}{n}<a_n$$
Combining this with $(*)$ we get that $a_{2n}<2a_n$.
