Induction for recurrence 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.
btw, i asked this question at maths stackexchange, and i got no good answer. That's why I am reposing here. 
 A: This proof is using strong induction: suppose the statement is true for $1,2,3,\dots,n-1$, and show that this implies that it is true for $n$.  Note that $\sqrt{n} < n$, so this is a valid inductive step.
See also, e.g., http://www.mathblog.dk/strong-induction/ for more on strong induction.
A: It is not clear exactly what the author had in mind. I think there are a couple of
possible interpretations.
One possibility is that the author was implicitly using an inductive step $n \rightarrow n^2$ rather than the usual $n \rightarrow n + 1.$
This works for numbers that are of the form $b^{2^k}$ for $k \in \mathbb N$ and a suitable base case $b.$  That is, the base case is really $k = 0$ (for which the problem size is $b^{2^0}$) and we do a simple induction on $k$ in $b^{2^k}.$
The disadvantage of this interpretation is that it doesn't say what happens with problems whose size isn't exactly of the form $b^{2^k}.$ If the answer is that we have to "pad out" the problem to the next larger such size, I don't think we get $n \lg \lg n$ time in general when $n$ can be any positive integer.
Another (more likely?) possibility is that "$\sqrt n$" (in the author's notation) is really
$\lceil \sqrt n \rceil,$ which could happen if the approach to a problem of size $k^2 + 1$ is to pad it out to a problem of size $(k + 1)^2.$
Then we can use strong induction to reason about $T(n)$ for any  positive integer $n.$
I suspect this is how such an algorithm would actually play out.
Since $\lceil \sqrt n \rceil < \sqrt n + 1$ for any positive integer $n,$
I think the inductive step would still hold. (I haven't checked.)
What we can't do (as far as I can see) is to prove case $T(n)$ for an arbitrary (but sufficiently large) integer $n$ in terms of $T(\sqrt n)$ if $\sqrt n$ means literally what it says, because in general  $\sqrt n$ is not an integer and therefore $\sqrt n \notin \{ 1, 2, 3, \ldots, n - 1 \}.$
