Inductive Proofs for Inequalities

We demonstrate a few interesting examples of induction relating to inequalities.

Example 1

To prove that $3^n\ge1+2n$3n≥1+2n for $n\ge1$n≥1

Testing for $n=1$n=1 and $n=2$n=2, we find $3\ge3$3≥3 and $9\ge7$9≥7 consecutively, and so it is true for the first two cases.

We now assume that its true for $n=k$n=k (where $k$k is a positive integer) so that $3^k\ge1+2k$3k≥1+2k. Then we attempt to prove, using that assumption, that $3^{k+1}\ge1+2(k+1)$3k+1≥1+2(k+1). In other words we will attempt to prove that $3^{k+1}\ge3+2k$3k+1≥3+2k. 

Often with the inequality types of induction, its more convenient to build a proof by starting from the assumption itself.

So starting from $3^k\ge1+2k$3k≥1+2k we write:

$3^k$3k	$\ge$≥	$1+2k$1+2k
$3\times3^k$3×3k	$\ge$≥	$3+6k$3+6k
$3^{k+1}$3k+1	$\ge$≥	$(3+2k)+4k$(3+2k)+4k
$\therefore3^{k+1}$∴3k+1	$\ge$≥	$(3+2k)$(3+2k)

Note in the second last line that we simply dropped the positive term $4k$4k, because if $3^{k+1}$3k+1 is greater than or equal to $(3+2k)+4k$(3+2k)+4k then it certainly must be greater than the smaller quantity $(3+2k)$(3+2k). 

So if it is true for $n=k$n=k then it is also true for $n=k+1$n=k+1. We know by direct substitution that it is true for $n=1$n=1 and $n=2$n=2, so in turn it must also true for $n=3$n=3, and in turn for $n=4$n=4, and $n=5$n=5 etc. In other words it is true for all $n$n.

 

Example 2

Prove by induction that $(1+x)^n\ge1+nx$(1+x)n≥1+nx where $x>-1$x>−1 and $n$n is a positive integer.

The restriction $x>-1$x>−1 is explained by considering the left hand side of the inequality.

The inequality is obviously true if $x$x was allowed to be zero, with $1^n\ge1$1n≥1. For $x<-1$x<−1 however $(1+x)^n$(1+x)n becomes negative for odd values of $n$n, and this can lead to a problem with the inequality. For example with $x=-3$x=−3 and $n=5$n=5, the inequality reads $(1-3)^5\ge1+(-15)$(1−3)5≥1+(−15) or when evaluated, $-32\ge-14$−32≥−14. This simple example demonstrates that it is not always true when $x<-1$x<−1.   

Continuing with the proof, for $n=1$n=1, we have $(1+x)^1=1+x$(1+x)1=1+x which is clearly true. For $n=2$n=2, we have $(1+x)^2=1+2x+x^2$(1+x)2=1+2x+x2 which, because $x^2$x2 is a non-negative term, is again greater than or equal to $1+2x$1+2x.

So it is definitely true for $n=1$n=1 and $n=2$n=2

Assume that its true for $n=k$n=k, so that $(1+x)^k\ge1+kx$(1+x)k≥1+kx 

The task then is to prove the statement for $n=k+1$n=k+1, namely that $(1+x)^{k+1}\ge1+(k+1)x$(1+x)k+1≥1+(k+1)x.

Taking the left hand side we have:

LHS	$=$=	$(1+x)^{k+1}$(1+x)k+1
	$=$=	$(1+x)^k(1+x)$(1+x)k(1+x)
	$\ge$≥	$(1+kx)(1+x)$(1+kx)(1+x)
	$\ge$≥	$1+x+kx+kx^2$1+x+kx+kx2
	$\ge$≥	$1+(k+1)x+kx^2$1+(k+1)x+kx2
	$\ge$≥	$1+(k+1)x$1+(k+1)x

The assumption that $(1+x)^k\ge1+kx$(1+x)k≥1+kx was inserted in line 3, and so it is true for $n=k+1$n=k+1 provided we accept thais assumption. But it is true for $n=2$n=2, so it must also be true for $n=3$n=3, and in turn for $n=4$n=4, etc. Hence it is true for all positive integers $n$n. 

Example 3

Prove that $4^{n-1}>n^2$4n−1>n2 for integer $n$n where $n\ge3$n≥3

For $n=1$n=1 and $n=2$n=2 the inequality doesn't work, and this explains the restriction on $n$n.

For $n=3$n=3, we have $4^2>3^2$42>32 which is clearly true.

So we assume it's true for $n=k$n=k, specifically that $4^{k-1}>k^2$4k−1>k2, and attempt to prove it for $n=k+1$n=k+1.

That is, we need to prove that, for $k\ge3$k≥3,  $4^k>(k+1)^2$4k>(k+1)2. 

The proof involves a few mathematical "tricks" that we will explain as we go.

Firstly:

$4^k$4k	$=$=	$4^{k-1+1}$4k−1+1
	$=$=	$4^{k-1}\times4^1$4k−1×41
	$=$=	$4^{k-1}\times4$4k−1×4

What this slight rearrangement does is to cleverly allow the assumption into the argument. Since $4^{k-1}>k^2$4k−1>k2, then we can write:

$\therefore4^k$∴4k	$>$>	$k^2\times4$k2×4

The right hand side becomes four lots of $k^2$k2, so we will strategically split these up, so that:

$4^k$4k	$>$>	$k^2+2k^2+k^2$k2+2k2+k2

Note that, certainly for $k\ge3$k≥3, $2k^2$2k2 (the second term on the right hand side) is greater than $2k$2k and $k^2$k2 (the third term) is greater than $1$1. So if we replace $2k^2$2k2 with $2k$2k and $k^2$k2 with $1$1, the right hand side reduces in size, so it must follow that:

$4^k$4k	$>$>	$k^2+2k+1$k2+2k+1
$\therefore4^k$∴4k	$>$>	$(k+1)^2$(k+1)2

Hence it is true for $n=k+1$n=k+1, and the rest of the proof follows easily.

The second strategy involving the replacement of $2k^2$2k2 and $k^2$k2 with $2k$2k and $1$1 respectively was strategic because it opened up a pathway directly into the statement we needed. Imagine the thinking of the person who first proved this.