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.

How do we go about this?


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


1 Answer 1


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) $.

About update

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

Example of using:

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.

  • $\begingroup$ 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? $\endgroup$
    – Jamāl
    Jul 20, 2022 at 12:47
  • $\begingroup$ 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)$. $\endgroup$
    – Jamāl
    Jul 20, 2022 at 12:52
  • $\begingroup$ 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$. $\endgroup$
    – zkutch
    Jul 20, 2022 at 12:52
  • $\begingroup$ 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. $\endgroup$
    – Jamāl
    Jul 20, 2022 at 12:54
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – zkutch
    Jul 20, 2022 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.