Proof by Strong Induction involving floors and logs. 
Consider the recurrence relation $a_1=1$, $a_n=na_{\lfloor n/2\rfloor}$ for $n\geq 2$.
Prove using strong induction, that $a_n\leq n^{\log_{2}n}$.

I am struggling to see how to deal with the floor function and how this might lead to a term with exponents and logs. Thanks for any help
 A: The inequality is certainly true for $n=1$. So suppose that
$n\geq 2$ and that the inequality is true
for every $k<n$, we must show that it is true for $n$.
Let $q=\lfloor \frac{n}{2} \rfloor$. Then $a_n=na_q \leq nq^{{\sf log}_2(q)}$
by the induction hypothesis. So it will suffice to show :
$$
nq^{{\sf log}_2(q)} \leq n^{{\sf log}_2(n)} \tag{1}
$$ 
Now $n\geq 2q$, so
$$
\frac{n^{{\sf log}_2(n)}}{nq^{{\sf log}_2(q)}}=
\frac{n^{{\sf log}_2(n)-1}}{q^{{\sf log}_2(q)}} 
\geq 
\frac{(2q)^{{\sf log}_2(2q)-1}}{q^{{\sf log}_2(q)}}=
\frac{2^{{\sf log}_2(q)}q^{{\sf log}_2(q)}}{q^{{\sf log}_2(q)}}=
2^{{\sf log}_2(q)} \geq 1
$$
which concludes the proof.
Here we used the fact that $x^y={\sf exp}(x{\sf log} y)$ is increasing in
both $x$ and $y$, when $x>0, y>1$.
A: Suppose that for every $k \lt n$ you have that $a_k \le k ^{log_{2}{k}}$. Now for 


*

*n even we have that $a_n=na_{\frac{n}{2}} \overset{\text{by induction hypothesis}}{\le} n (\frac{n}{2})^{log_{2}{\frac{n}{2}}} \le n (n)^{log_{2}{\frac{n}{2}}} = n^{log_{2}{\frac{n}{2}} + 1} = n^{log_{2}{n}}$

*n odd we have that $a_n=na_{\frac{n - 1}{2}} \overset{\text{by induction hypothesis}}{\le} n (\frac{n-1}{2})^{log_{2}{\frac{n-1}{2}}} \le n (n)^{log_{2}{\frac{n-1}{2}}} = n^{log_{2}{\frac{n-1}{2}} + 1} $$= n^{log_{2}{(n-1)}}\le n^{log_{2}{n}}$

