Technique

Compare $a^{n}$ with $n^{k}$ over the natural numbers

Algebra • Expressions • Inequalities

Statement

To decide

a^{n} > n^{k}

for

a > 1

and fixed

k

, test the small values of

n

one by one, then close the tail: if

a^{N} > N^{k}

at some

N

and

a \geq (1 + \frac{1}{n})^{k}

for every

n \geq N

, then one step multiplies the left side by at least as much as the right, so the inequality holds for every

n \geq N

. Small

n

must be tested individually, because that is where the two sides can cross.

How to use it

1Tabulate both sides for $n = 1, 2, 3, \dots$ until the exponential is clearly ahead; the crossings all live in that range.
2Close the tail with the per-step growth factors: the left side gains a factor $a$ , the right side a factor $(1 + \frac{1}{n})^{k}$ , which shrinks towards $1$ as $n$ grows.
3Check equality separately: a strict inequality fails where the two sides are equal, and that is the usual trap.
4One failing value is enough to refute a claim made for all $n$ ; one succeeding value proves nothing about the rest.

Worked example

For which natural numbers

n

2^{n} > n^{2}

Step-by-step

1
$n = 1$ : $2 > 1$ , true. $n = 2$ : $4 > 4$ , false. $n = 3$ : $8 > 9$ , false. $n = 4$ : $16 > 16$ , false. $n = 5$ : $32 > 25$ , true.
Why: The two sides cross twice among the small values, so each has to be tested on its own.
2
For $n \geq 5$ : $(1 + \frac{1}{n})^{2} \leq (\frac{6}{5})^{2} = 1.44 < 2$
Why: Each step multiplies $2^{n}$ by $2$ and $n^{2}$ by less than $1.44$ , so the lead at $n = 5$ can never be lost.
3
$2^{n} > n^{2}$ exactly for $n = 1$ and $n \geq 5$

Answer

n = 1

and every

n \geq 5

Watch out

The tail argument needs the growth factor compared at the smallest

n

in the tail, since

(1 + \frac{1}{n})^{k}

is largest there. Stopping at the first success is the common error:

2^{1} > 1^{2}

holds but

2^{2} > 2^{2}

does not.

Builds on

Power of a power, and the move to a common base

Also known as

compare 2^n and n^2, exponential beats polynomial, 3^n versus n^3, which grows faster, inequality for all natural numbers, test small values then close the tail

Appears in past papers

2019 (I)

Q29