# Proving an asymptotic bound with induction

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

• 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. Sep 15 at 17:13
• @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? Sep 15 at 17:18
• 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. Sep 15 at 17:23
• @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? Sep 15 at 17:45
• 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)$ Sep 15 at 17:55