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
Best Answer
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$.