1. Induction question..

Hello,

I just have a question about Induction.

Lets say we we need to prove that N^3 > N^2 + 3, when N >= 2.

So we start with the base case: where N = 2.. obviously 2^3 is > N^2 + 3.. so the base case holds.

Inductive hypothesis: we assume that for all K >= 2 theres K^3 > K^2 + 3.

Inductive Step: we prove that (K+1)^3 > (K+1)^2 + 3.

So now my question is how to proceed from here ???
What should I start with ??? Should I start with the inductive hypothesis and try to manipulate it and turn it into the inductive step goal.. or should i start with the inductive step ???? or basically what ??? and how do we use the inductive hypothesis to prove the goal ???

Any help would be appreciated... thanks in advance.

2. Originally Posted by MMM88
Hello,

I just have a question about Induction.

Lets say we we need to prove that N^3 > N^2 + 3, when N >= 2.

So we start with the base case: where N = 2.. obviously 2^3 is > N^2 + 3.. so the base case holds.

Inductive hypothesis: we assume that for all K >= 2 theres K^3 > K^2 + 3.
Almost. We assume that there exists some number K such that $K^3 > K^2 + 3$ holds. (We could also use "strong induction" and assume that there is a number K such that $x^3 > x^2 + 3$ for all $K \geq x \geq 2$, but we don't need anything like that here.)

Now we need to show that
$(K + 1)^3 > (K + 1)^2 + 3$
Look at the LHS:
$(K + 1)^3 = K^3 + 3K^2 + 3K + 1$

By hypothesis $K^3 > K^2 + 3$, so we know that
$(K + 1)^3 = (K^3) + 3K^2 + 3K + 1 > (K^2 + 3) + 3K^2 + 3K + 1$

So
$(K + 1)^3 > 4K^2 + 3K + 4$

Now, how does $4K^2 + 3K + 4$ compare to $(K + 1)^2 + 3 = K^2 + 2K + 1 + 3 = K^2 + 2K + 4$? It is greater, of course. So we have, finally:
$(K + 1)^3 > 4K^2 + 3K + 4 > (K + 1)^2 + 3$
or
$(K + 1)^3 > (K + 1)^2 + 3$

Since the theorem is true for K = 2, it is true for K = 3, 4, ...

-Dan