Prove n n² for n>=4
We begin by showing that it is true for the smallest possible
value of n, which is 4:
4 4²
24 > 16 which is true.
Assume for n <= k
(1) k k² <--- we are assuming this.
We need to show that assumption (1) leads to
(2) (k + 1) (k + 1)² <--- we do not know this yet!
Since (k + 1)² = k² + 2k + 1, the 2k + 1 tells us that we
should add 2k + 1 to both sides of assumed inequality (1):
(3) k! + 2k + 1 > k² + 2k + 1 = (k + 1)² <--- we know this
Now we just need to show that the left side of (3) is less
than the left side of (2)
That is, we need to show that
(4) k! + 2k + 1 < (k + 1)! <--- we do not know this yet
which is equivalent to
(5) k! + 2k + 1 < (k + 1)k! <--- we do not know this yet
which is equivalent to
(6) k! + 2k + 1 < k·k! + k! <--- we do not know this yet
which is equivalent to
(7) 2k + 1 < k·k! <--- we do not know this yet
Which is equivalent to the following (upon dividing through by k):
(9) 2 + < k! <--- we DO know this.
We DO know (9) is true. Here's why:
The left side is always less than 3 and since k >= 4, the right side k! is
always 4! = 24 or greater so we do know (9) is true.
Now since all those inequalities are equivalent we can reverse the
steps
(9) 2 + < k! is true, therefore, multiplying thru by k,
(8) 2k + 1 < k·k! is true, therefore adding k! to both sides:
(7) k! + 2k + 1 < k·k! + k! is true, therefore factoring the right:
(6) k! + 2k + 1 < k!(k + 1) is true, and the right side is (k + 1)!, so
(5) k! + 2k + 1 < (k + 1)k! is true. So:
(4) k! + 2k + 1 < (k + 1)! is true, which is the same as
(k + 1) k! + 2k + 1
and since (3) is true, which is
(3) k! + 2k + 1 > k² + 2k + 1 = (k + 1)², we have
(k + 1) k! + 2k + 1 > k² + 2k + 1 > (k + 1)²
which is what we needed to prove.
The proof of the other one is similar. It amounts to taking
the inequality you have to prove, simplifying it using equivalent
inequalities to get something that you know is true, then you
reverse the steps.
Edwin