1
$\begingroup$

i want to prove that $3^n$ has a greater growth than $n2^n$ or $3^n = O(n2^n)$. but how can i do it mathematically? by induction or contradiction or other ways of proof.

$\endgroup$
2
  • 1
    $\begingroup$ Use definition? $\endgroup$
    – Evil
    Commented Mar 25, 2018 at 19:38
  • $\begingroup$ yes, every way which is mathematically true. $\endgroup$
    – Daniel
    Commented Mar 25, 2018 at 19:58

1 Answer 1

2
$\begingroup$

One simple way would be divide both sides by $2^n$ to get $n$ and $(1.5)^n$. You can simply take a limit of $l i m_{n\to\infty} \frac{(1.5)^n}{n} = \infty$ To show that $(1.5)^n$ grows larger. This limit holds for any number larger than 1.

$\endgroup$
3
  • $\begingroup$ Thanks for taking the time to post an answer! Note that we have collected a number of reference questions that provide vetted answers that cover many exercise problems, including this one. Posting answers to every similat question is probably a waste of time. $\endgroup$
    – Raphael
    Commented Mar 25, 2018 at 20:22
  • $\begingroup$ Oh sorry. Did not think of referencing a more general question initially. Thank you for pointing that out. Should this answer be erased? $\endgroup$
    – sunnytheit
    Commented Mar 25, 2018 at 20:28
  • $\begingroup$ i liked to prove it by contradiction or induction, not only the common ways. is that against of rules? $\endgroup$
    – Daniel
    Commented Mar 26, 2018 at 9:02

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