Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$
To prove $r_n = O(\lg \lg n)$ by induction on $n$, suppose $r_n \le c (\lg \lg n)$ is true for $n$ and consider $r_{n+1}$:

$$r_{n+1} = 1 + r_{\lfloor \sqrt{n+1} \rfloor} \le 1 + c(\lg \lg (\lfloor \sqrt{n+1} \rfloor)) \le 1 + c(\lg \lg \sqrt{n+1}) \\ = 1 + c(\lg (1/2\lg (n+1)) = 1 + c(-1 + \lg \lg(n+1)) \\ = 1-c + c(\lg \lg (n+1)) $$

Take $c = 1$.



If you don't stick to the mathematical induction, there is an easier method with less computation by "change-of-variable" (ignore the things of "taking floor"):

Take $m = \lg n$. Consider another sequence $s$ with $s(m) = r(2^{m})$:

$$r(2^{m}) = 1 + r(2^{m/2}) \Rightarrow s(m) = 1 + s(m/2) = \Theta(\lg m) \quad \text{(by the master theorem)}$$

Substitute $m = \lg n$ into the last equation, we have $r(n) = \Theta(\lg \lg n)$.