If $a \in \mathbb N$ with $a \geq 3$, then $a^n > n^2$ for all $n \in \mathbb N$.

Question

I searched for $a^n > n^2$ but didn't find anything relevant.

This is Exercise $3 (b)$ from page $43$ of Analysis I by Amann and Escher.

Exercise:

Verify using induction that if $a \in \mathbb N$ with $a \geq 3$, then $a^n > n^2$ for all $n \in \mathbb N$.

More information:

In this book we use $\mathbb N = \{ 0, 1, 2, \dots \}$.

My attempt:

Base case: It's clearly true that $a^0 > 0^2$.

Inductive step: Assume the result is true for $n$. Then for $n + 1$ we get

\begin{align*} a^{n+1} &= a^n \cdot a\\ &> an^2\\ &\geq 3n^2. \end{align*}

I need to show that $3n^2 \geq n^2 + 2n + 1 = (n + 1)^2$. This is equivalent to showing that $2n^2 \geq2n + 1$. My problem is that this is not true for any $n \in \mathbb N$.

How do I rescue this? There is probably something simple I'm overlooking. I appreciate any help.

Answer 1

You can simplify with $$a^n>n^2\iff b^n>n$$ where $b=\sqrt a$.

We need to prove that $$b^n>n\implies b^{n+1}=b\,b^n>b\,n>n+1$$

and this is true when $$n>\frac1{b-1}.$$

For the smallest $b$ ($=\sqrt3$), $n>1$ works.

Answer 2

Let your base case be $n= 2$.

Prove it is true for $n =0,1$ individually and separately.

Base case: $n = 2$ then $a^2 \ge 3^2 =9 > 4 =2^2$.

Inductions step: If $a^n > n^2$ and $n\ge 2$ then

$a^{n+1}\ge 3*a^n > 3*n^2 = n^2 + n^2 + n^2 \ge n^2 + 2n + 2n\ge n^2 +2n + 4 >n^2 + 2n + 1=(n+1)^2$.

So by induction we proved the statement is true for all $n \ge 2$.

So how do we prove it for $n < 2$..... Hmmm.... well maybe we....just do the effing things.

If $n = 0$ then $a^0 =1 > 0=0^2$. And if $n=1$ then $a^1=a\ge 3 > 1=1^2$.

So it's true for all $n\ge 2$ and it's true for $n=0,1$ and .... that's everything we need.

=====

Actually we can maybe do it for base case $n$ and $n\ge 1$.

$a^{n+1}\ge 3a^n> 3n^2$ so $a^{n+1}\ge 3n^2 + 1 = n^2 + (n^2+1) + n^2= n^2 + n(n+\frac 1n) +n^2\ge n^2 + n*2 + 1$ with equality holding only if $n=1$ and $a^{n+1}=3n^2 + 1$ but $a^2=4$ implies $a=2< 3$ so strict inequality holds.

But I don't see how we can do induction step without assume $n$ is at least $1$.

Answer 3

Clearly it holds for $n=0$ and $n=1$ since $a^{0}=1>0^{2}=0$ and $a^{1}\geq 3>1.$

Then since $2(n-1)^{2}\geq 0$ we have $2n^{2}\geq4n-2>2n+1 $ for $n\geq 2$.

Answer 4

As others have noted, it's OK to start an induction proof with more than one "base" case. If you want to avoid doing so, say for the sake of elegance, here are two different approaches to a proof.

Approach 1: Start with a lemma: $3^n\ge n+1$ for all $n\in\mathbb{N}$. The induction proof for this has base case $3^0=1\ge0+1$, followed by

$$3^{n+1}=3\cdot3^n\ge3(n+1)=3n+3\ge n+2=(n+1)+1$$

To prove $3^n\gt n^2$ for all $n$, the inductive proof now goes $3^0=1\gt0=0^2$ and

$$3^{n+1}=3\cdot3^n=2\cdot3^n+3^n\gt 2n^2+(n+1)=n^2+(n^2+n)+1\ge n^2+2n+1=(n+1)^2$$

where the key inequality, $2\cdot3^n+3^n\gt2n^2+(n+1)$, combines the induction step $3^n\gt n^2$ and the lemma $3^n\ge n+1$.

Approach 2: Prove the (seemingly) stronger statement $3^n\ge n^2+1$ (from which $3^n\gt n^2$ follows automatically). The base case here is $3^0=1\ge0^2+1$, and the induction is

$$3^{n+1}=3\cdot3^n\ge3(n^2+1)=n^2+2n^2+2+1\ge n^2+2n+1+1=(n+1)^2+1$$

Remark: Actually $3^n\ge n^2+1$ is equivalent to $3^n\gt n^2$, not stronger, since both $3^n$ and $n^2$ are integers.