1
$\begingroup$

I actually thought about this after reading the proof for the Immerman–Szelepcsényi theorem (though it is not necessarily related).

Let us define a series: $a_1,...,a_n$ , where: $$a_{i+1} = a_i + \log{n}$$ and: $$a_1=\log{n}$$ Obviously we get: $a_n = n\log{n}$.

However, let us define the following inductive process:

We will try to prove $a_i = O(\log{n})$ for $i=1,...,n$.

The induction basis is pretty straight forward, we get $a_1 = \log{n} = O(\log{n})$.

Now, let's assume correctness for $j\le i$ and let's prove for $i+1$. Since by induction hypothesis we get $a_i = O(\log{n})$, we get that $a_{i+1} = a_i + \log{n} = O(\log{n}) + \log{n} = O(\log{n})$.

So by proving the induction, we conclude that: $$a_n = O(\log{n})$$

This is obviously wrong, but where is the mistake in this induction? I guess it has something to do with the asymptotic bounds, but if the the basis is correct, and the inductive step (based only on the induction hypothesis) is correct, the induction should be too. What am I missing?

Thanks!

$\endgroup$
7
  • $\begingroup$ I don't see why this argument is wrong? $\endgroup$ Jun 29, 2018 at 9:38
  • 1
    $\begingroup$ One thing I noted is that you mess up the indices a little bit. Since $a_m = m\log n=\OOO(m)$. $\endgroup$ Jun 29, 2018 at 9:41
  • $\begingroup$ @StanTendijck not sure about your comment on the indices (the mathjax didn't parse, and I didn't use an $m$ index during my proof), but for your first comment, this is wrong since $n\log{n} \ne O(\log{n})$ $\endgroup$
    – Mickey
    Jun 29, 2018 at 9:45
  • $\begingroup$ I am sorry, what I wanted to say is that $a_n$ is indeed equal to $n\log n$. However, $a_m$ is not equal to $m\log m$ but equal to $m\log n$ which is of order $m$. $\endgroup$ Jun 29, 2018 at 9:50
  • $\begingroup$ You can prove that by induction $a_i \leq C i$ (with $C=\log n$). $\endgroup$ Jun 29, 2018 at 9:52

1 Answer 1

2
$\begingroup$

For every $n\in\mathbb{N^+}$ you can define the sequence $\{a_k\}$ $$ \begin{cases} a_{k+1}(n)=a_k(n)+\log n \\ a_1(n)=\log n \end{cases} \implies a_k(n)=k\log n \quad\forall k\in\mathbb{N^+} $$

Notice that the expression "$a_k= O(\log n)$" makes no sense because the value of $n$ is fixed. The asymptotic behaviour of $a_k$ is $O(k)$.

Now, for every fixed value of $k$, consider the sequence $\{b_n\}$ defined by $$b_n(k)\colon=a_k(n)=k\log n \quad\forall n\in\mathbb{N^+}$$

Of course $b_n=k\log n=O(\log n)\quad\forall k\in\mathbb{N^+}$.

The sequence $\{b_n\}$ must not be confused with the different sequence $\{c_n\}$: $$ c_n\colon= a_n(n)=b_n(n)=n\log n\ne O(\log n) $$

In this case both $k$ and $n$ grow to infinity and their values are not independent.

When you write "$a_n$" it's ambiguous: do you mean $b_n$ or $c_n$? This is what you need to clarify in your proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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