## Induction for inequalities

Complex numbers, rational functions, logarithms, sequences and series, matrix operations, etc.
ikemup
Posts: 1
Joined: Tue Nov 03, 2009 2:32 pm
Contact:

### Induction for inequalities

Hello, I am having trouble understanding inequalities and induction. I have reviewed numerous sites, but just don't "get it". I feel that I understand what induction accomplishes, and find equalities fun and easy, but I seem to be missing some fundamental mechanics for inequalities.

In the example below (bottom, from http://www.purplemath.com/modules/inductn3.htm), I am fine with proving the basis, and when working, it follows as I would expect that if f(k) = 4k, then the next in the series, f(k+1) = 4k + 4. However, what I don't understand is this, which in turn lead to confusion for the rest of the example:

Since k > 5, then 4 < 32 < 2k. Then we get

2k + 4 < 2k + 2k = 2×2k = 21×2k = 2k+1

Why here is it 2k + 4 < 2k + 2k? Why, like equalities, does it not stay as 4k + 4 < 2k + 4? I don't understand why/how the transformation occurred on each side of the inequality.

I'm sure the explanation is embarrassingly simple, but that's why I came here for help, right?

Thanks!

Full example from http://www.purplemath.com/modules/inductn3.htm:

* (*) For n > 5, 4n < 2n.

This one doesn't start at n = 1, and involves an inequality instead of an equation. (If you graph 4x and 2x on the same axes, you'll see why we have to start at n = 5, instead of the customary n = 1.)

Let n = 5.

Then 4n = 4×5 = 20, and 2n = 25 = 32.

Since 20 < 32, then (*) holds at n = 5.

Assume, for n = k, that (*) holds; that is, assume that 4k < 2k

Let n = k + 1.

The left-hand side of (*) gives us 4(k + 1) = 4k + 4, and, by assumption,

[4k] + 4 < [2k] + 4

Since k > 5, then 4 < 32 < 2k. Then we get

2k + 4 < 2k + 2k = 2×2k = 21×2k = 2k+1

Then 4(k+1) < 2k+1, and (*) holds for n = k + 1.

Then (*) holds for all n > 5.

stapel_eliz
Posts: 1628
Joined: Mon Dec 08, 2008 4:22 pm
Contact:
The actual statement was more along the lines of the following:
$\mbox{Prove, for }\, n\, >\, 5,\, \mbox{ that}\, 4n\, <\, 2^n$

$\mbox{This rule doesn't start at "}n\, =\, 1\mbox{", and involves an inequality}$

$\mbox{instead of an equation. (If you graph }\, 4x\, \mbox{and}\, 2^x\, \mbox{ on the same}$

$\mbox{axes, you'll see why we have to start at }\,n\, =\, 5\,\mbox{ instead of the}$

$\mbox{customary }\,n\, =\, 1\mbox{.)}$

$\mbox{Let }\, n\, =\, 5.\, \mbox{ Then }\, 4n\, =\, 4\times 5\, =\, 20,\, \mbox{ and }\, 2^n\, =\, 2^5\, =\, 32.$

$\mbox{Since }\, 20\, <\, 32,\, \mbox{ then the formula holds at }\, n\, =\, 5.$

$\mbox{Assume, for }\, n\, =\, k,\, \mbox{ that }\, 4k\, <\, 2^k\mbox{. Let }\, n\, =\, k\, +\, 1.$

$\mbox{The left-hand side of the formula gives us }\, 4(k\, +\, 1)\, =\, 4k\, +\, 4$

$\mbox{and, by assumption, }\, 4k\, +\, 4\, <\, 2^k\, +\, 4$
This is by substitution: We assumed that 4k < 2k, so this is just plug-n-chug from the assumption step.
$\mbox{Since }\, k > 5,\, \mbox{ then }\, 4\, <\, 32\, \leq\, 2^k.$
Four is always less than thirty-two, and 32 = 25 has to be no more than 2k, because 5 < k at this point.
$\mbox{Then we get:}$

$2^k\, +\, 4\, <\, 2^k\, +\, 2^k\, =\, 2\times 2^k\, =\, 2^1 \times 2^k\, =\, 2^{k\, +\, 1}$
The first part is from the substitution above; the second part is from the fact that 4 = 22 < 25 < 2k, and the rest is by properties of exponents, addition, and multiplication.