Function Growth Proof

Question

Prove: $\forall a \in \mathbb{R}^+, \exists n_0 \in \mathbb{N}, \forall n \in \mathbb{N}, n\geq n_0 \implies an \leq 2^n$

The hints are:

• Use induction on $n$
• it’s easier if you don’t try to find the smallest possible $n_0$

I don't know where to start other than setting up the induction. When it comes to the proof, I am stuck!

Answer 1

Additional hints:

$a(n+1) = an + a\cdot 1$

Meanwhile $2^{n+1} = 2\cdot 2^n = 2^n + 2^n$

We should be able to convince ourselves that $a\leq an$. Supposing that we were able to compare $an$ and $2^n$, can we use this knowledge to compare $a(n+1)$ and $2^{n+1}$?

---

As far as "don't try to find the smallest possible $n_0$" that is very good advice. Following that advice, let's consider what happens if we take $n_0$ to be $\lceil a\rceil$ itself. Then how does $an_0$ compare to $2^{n_0}$?

Is it true that $n^2\leq 2^n$ for any positive integer $n$ greater than $3$? If you don't know that this is true already, then perhaps try proving this by induction as well.

---

Full answer: Try to finish the problem on your own before looking here.

We wish to prove that for any $a\in \Bbb R^+$ there exists an $n_0$ such that for all $n\geq n_0$ we have $an\leq 2^n$.

Claim: Letting $n_0 = \max(\lceil a\rceil,4)$ suffices.

$~$

Base case: We have $an_0 \leq n_0^2$. Remembering that $n^2\leq 2^n$ for all positive integers $n$ greater than $3$ (proof left to reader) it follows that $n_0^2\leq 2^{n_0}$ and thus $an_0\leq 2^{n_0}$.

$~$

Inductive step: Supposing as our induction hypothesis that $an\leq 2^n$ is true for some particular value of $n$, we recognize that $a(n+1) = an + a \leq an + an$ which by applying our induction hypothesis to each of these terms is less than $2^n + 2^n = 2^{n+1}$