0

The true statement I fail to prove: $\forall b, c \in \mathbb{R}, b \gt 1: \exists n_0 \in \mathbb{N}: \forall n \ge n_0: n^c \le b^n$. Basically, as far as I can see, it says that every polynomial eventually grows slower than every $(> 1)$ exponential (when $n \in \mathbb{N}$).

I don't need the answer, I need a hint. Seems like $\delta(n) = f(n + 1) - f(n)$ is a good starting point? By binominals, I would get that $\delta_{n^c}(n) = k_{c - 1}n^{c-1} + k_{c - 2}n^{c-2} + ... + k_2n^{2} + k_1n + k_0$ and $\delta_{b^n}(n) = b^n(b -1 )$. At this point I got stuck.

Please, help.

Zazaeil
  • 1,518

1 Answers1

3

This statement is false.

Indeed, let's suppose that there exists such a $n_0$. Then you would have, for $n = n_0 +1$, $b= n_0 + 1$, and $c = n_0 +2$, the inequality $$(n_0 + 1)^{n_0 +2} \leq (n_0 + 1)^{n_0 +1}$$

which is obviously incorrect.

I guess the "good" statement is $\forall b,c$, $\exists n_0$ such that ...

TheSilverDoe
  • 29,720
  • yeah, typo. will correct myself. – Zazaeil Mar 05 '19 at 14:05
  • There was an edit in the question which makes this answer rather confusing and technically wrong (while it was presumably correct at the time of posting). Please edit for clarification. – quarague Mar 05 '19 at 14:34