0
$\begingroup$

Suppose we want to prove by induction that $f(n) \in \Theta(g(n))$. How should the induction proof be set up? I'm tempted to say that the base case should prove that $f(1) \in \Theta(g(1))$ and the inductive step should be to prove that if $f(k) \in \Theta(g(k))$ for some $k\in\mathbb N$, then $f(k+1) \in \Theta(g(k+1))$. However, I think this wouldn't make sense because both previous statements would always be true since a constant is always $\Theta (1)$.

$\endgroup$
5
  • 2
    $\begingroup$ Formally there "is not" $n$ variable in $f(n) \in \Theta(g(n))$, or ,more exactly, it is dummy, bound variable. Formally it is $f(n) \in \Theta(g(n)), n \to \infty$ or $f \in \Theta(g)$. To use induction, firstly, write down exact definition and then apply induction with respect to it. $\endgroup$
    – zkutch
    Sep 15 at 17:13
  • $\begingroup$ @zkutch: I know that for induction I have to find a proposition that depends on some parameter $n$, say $P(n)$. What would be the "n" in this case? $\endgroup$
    – Keio203
    Sep 15 at 17:18
  • 2
    $\begingroup$ Let it write down: $\exists C>0, \exists N\in\mathbb{N}$ such that $\forall n >N, f(n)\leqslant C g(n)$. Induction you use to part after words "such that". Remember, that induction can start from any fixed natural number, not only on $1$, and the result will be true up to that fixed natural number. $\endgroup$
    – zkutch
    Sep 15 at 17:23
  • $\begingroup$ @zkutch: Okay, so the proposition $P(n)$ we have to induct on should be $f(n) \leq C g(n)$. The base case should be to show that $f(N) \leq C g(N)$ for some $N$. The inductive step should be to assume that $f(n) \leq C g(n)$ is true for some $n \geq N$ and to conclude that $f(n+1) \leq C g(n+1)$ is true. Is this correct? $\endgroup$
    – Keio203
    Sep 15 at 17:45
  • 1
    $\begingroup$ Yes, it is correct. Only I prefer last part to say so: for $n>N$ we have $f(n) \leq C g(n)$ implies $f(n+1) \leq C g(n+1)$ $\endgroup$
    – zkutch
    Sep 15 at 17:55

0

Your Answer

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