How to formally prove that $f(n)=\Theta f(n+1)$?

It's supposed to be easy, but I still can't get it. Thank you very much.

  • 1
    $\begingroup$ Beware the abuse of notation there. $\endgroup$ – Raphael May 19 '12 at 18:41

This depends on the sequence $(f(n))$. For example:

  • If $f(n)=n!$ then $f(n)\ll f(n+1)$ hence $f(n)\notin\Theta(f(n+1))$.
  • If $f(n)=\frac1{n!}$ then $f(n)\gg f(n+1)$ hence $f(n)\notin\Theta(f(n+1))$.
  • If $f(n)=a^n$ with $a\ne0$ then $f(n)=\frac1af(n+1)$ hence $f(n)\in\Theta(f(n+1))$.
| cite | improve this answer | |
  • $\begingroup$ oh OK then. I was wrong I thought they are Θ of each other. Thank you very much!!! $\endgroup$ – Talom May 19 '12 at 15:45
  • 1
    $\begingroup$ This (abuse of) notation suggests that numbers can be in Landau relations. I think you should properly define the two sequences behind the scenes as to not confuse anybody. $\endgroup$ – Raphael May 19 '12 at 18:41

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.