I'm trying to understand an induction proof that aims to prove some function is in $O(n\log{ n})$.
It's on page 5 of this PDF: https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf
The function is
$$T(n)=\sqrt{n}\, T(\sqrt{n}) +n$$
We want to prove that
$$T(n) \leq an \log{ n}$$ for sufficiently large $n$ and some constant $a$ to be determined later.
The author uses induction as follows: \begin{align*} T(n) &= \sqrt{n}\,T(\sqrt{n}) +n \\ &\le \sqrt{n}\,a\sqrt{n}\, \log{\sqrt{n}} +n \qquad \text{[induction hypothesis]} \\ &= (a/2)n \log{ n} +n \\ &\le an \log{n } \end{align*}
First, this is an induction proof, so there should be a base case, but i understand that one needn't prove the base case first. That can always be done later, as the author acknowledges further down the page.
Second, and this is what i don't understand, how is this induction if the proof isn't going from some $n$ to an $n+1$? Is the jump from $\sqrt{n}$ to $n$ equivalent to the jump from $n$ to $n+1$? Or is something else going on.