Use induction to show $a_n$ is no greater than $4\log_2(\log_2(n))$

Question

Given a sequence where $a_1 = 1$ and $a_n = 1+ a_{\lfloor\sqrt{n}\rfloor}, n\geqslant 2$.

Show that $a_n \leqslant 4\log_2\log_2(n), \forall n \geqslant 3$.

Here's my idea:

Base case is $n=3, a_3 = 2 \leqslant 4\log_2\log_23 = 2.6576$

Suppose this satisfies for $n=k, k \in \mathbb{N}$, want to show case $n = k +1$

Case 1: if $a_{k+1} = a_k$, then $a_{k+1}=a_k \leqslant 4\log_2\log_2k \leqslant 4\log_2\log_2{(k+1)}$ which is trivial.

Case 2: if $a_{k+1} = a_k + 1$...? This is where I stuck.

Thanks in advance.

Answer 1

$$ 4\log_2\log_2(k+1) = 4\log_2\log_2(\sqrt{k+1})^2 = 4\log_2(2\log_2\sqrt{k+1}) = $$ $$ = 4 + 4\log_2\log_2\sqrt{k+1} \gt 1 + 4\log_2\log_2\lfloor\sqrt{k+1}\rfloor \ge 1 + a_{\lfloor\sqrt{k+1}\rfloor} = a_{k+1} $$