Induction for recurrence

Question

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.

Answer 1

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.

Answer 2

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 \}.$