# How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method?

Suppose you have to prove the solution to the following recurrence by Induction,

$$T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1 \end{cases}$$ Here, $$\Theta(1)$$ and $$\Theta(n)$$ are notational abuse and they represent arbitrary positive constant and arbitrary linear function respectively.

First, we guess the solution, $$T(n)=O(n\log n)$$ which expanded, $$T(n)\le cn\log n \quad \forall n\ge n_0,\text{where }c>0, n_0\in \mathbb N$$

Now, we want to prove $$\forall nP(n)$$, where $$P(n):T(n)\le cn\log n \quad \forall n\ge n_0,\text{where }c>0, n_0\in \mathbb N$$

We will assume $$P(k)$$ for some $$k$$ and show $$P(k+1)$$. But what does it mean to assume $$P(k)$$ for some $$k$$ here? The expression $$\forall k\ge n_0$$ hurts by brain since we have taken $$k$$ to be some natural number and prefixing it with universal quantifier doesn't make sense to me.

Update

Actually the problem is with $$P(n)$$. It cannot contain quantifiers. It is atomic in First-order Logic.

What you asking about is mathematical induction theorem, more known as mathematical induction principle. It states, that $$\begin{cases}{} P(n_0) \text{ true} & \\ (\forall n \geqslant n_0)\big(P(n)\Rightarrow P(n+1)\big) & \end{cases} \Rightarrow (\forall n\geqslant n_0)P(n)$$

verbally it means, that for proving $$(\forall n \geqslant n_0)P(n)$$ is enough to prove two sentences: $$P(n_0)$$ and implication $$(\forall n \geqslant n_0)\big(P(n)\Rightarrow P(n+1)\big)$$. In last one $$n$$ is, so called, bound variable, dummy variable, and can be replaced with any other letter except $$P$$ and $$n_0$$. For example it same with $$(\forall k \geqslant n_0)\big(P(k)\Rightarrow P(k+1)\big)$$.

Sentence under consideration is $$T(n)=O(n\log n), n\to \infty\quad (2)$$ and it's definition, of course contain quantifiers. As $$n$$ is bound variable in $$(2)$$, then it is not fully correct to denote it by $$P(n)$$, because, really, it does not contain $$n$$. Exact is to write $$T\in O(f)$$, where $$f(x)=x \log x$$.
Let me show how is it possible to use math. induction with sentences type $$f\in O(g)\quad(3)$$. Assume $$f(n)=g(n)=n$$. Formally $$(3)$$ is following: $$\exists c>0, \exists n_0 \in \mathbb{N}, \forall k > n_0, k\leqslant c\cdot k\quad (4)$$ All variables used are bound except $$\mathbb{N}$$. Let's choose $$c=1=n_0$$, denote by $$P(k)$$ sentence $$k\leqslant k$$ and start proof of sentence $$\forall k > 1,P(k)$$, using math. induction with respect to $$P$$. Because holds $$P(1)$$ and $$(\forall k \geqslant 1)\big(P(k)\Rightarrow P(k+1)\big)$$, then proof is finished trivially.
• I understand what mathematical induction is. My confusion is in the following statement. "Assume $P(k)$ is true for some $k\in \mathbb N$". This is same as "Assume that $T(k)\le ck\log k \quad \forall k\ge n_0,$ where $c>0, n_0\in \mathbb N$ is true for some $k\in \mathbb N$". What does "$\forall k\ge n_0$ but for some $k\in \mathbb N$" mean? Jul 20, 2022 at 12:47
• As you pointed out, we want to prove $(\forall k \geqslant n_0)\big(P(k)\Rightarrow P(k+1)\big)$. For this, we assume $P(k)$ for some $k$ and not $\forall k\ge n_0 P(k)$. Jul 20, 2022 at 12:52
• Statement should be following "Consider any $k \geqslant n_0$. Assume $P(k)$ and prove $P(k+1)$". Word "some" in this context means "any", because you take "some", but without restriction other then $\geqslant n_0$. Jul 20, 2022 at 12:52
• We do consider any $k\ge n_0$. But when we assume $P(k)$, $k$ is a fixed arbitrary natural number. Since after this we want to show $P(k+1)$, it wouldn't make any sense to let $k$ vary in the middle of proof. Jul 20, 2022 at 12:54
• Usually part with quantifiers are first in sentence: so, assume we want to prove $\exists c>0, \exists n_0 \in \mathbb{N}, \forall k > n_0, P(k)\quad (1)$. Now this can be proved with several methods. One of them induction. I speak about using induction for whole $(1)$. Jul 20, 2022 at 13:28