1. ## Complete/Simple Induction

Here's the question:

Use induction to prove that for every integer $n \geq 4$, $3^n > n^3$.

Firstly, I'm confused whether to use the simple induction or the complete induction for this problem. I will try the simple one:

Base case: let $n \in N$ and let P(n) be the statement:

" $n \geq 4$, $3^n > n^3$"

Since $n \geq 4$ I can't use P(1) as the base case so I'll do P(4) in its stead:

$3^4 > 4^3 \Rightarrow 81>64$

Inductive step:
Suppose $k \geq 4$ and P(k) is true. So $3^k > k^3$

Now we consider P(k+1)

$3^{k+1} > (k+1)^3$

$LHS = 3^k .3 > k^3 +1 = RHS$

What else can be done here to prove the inequality?

any help is appreciated

2. You know from the base case that $3^k > k^3$. You also know that $k \geq 4$ so that gives you $3^{k+1} = 3 \cdot 3^k > 3k^3 > 2k^3 + 1 > k^3 + 1$

3. Originally Posted by Defunkt
You know from the base case that $3^k > k^3$. You also know that $k \geq 4$ so that gives you $3^{k+1} = 3 \cdot 3^k > 3k^3 > 2k^3 + 1 > k^3 + 1$

errr ... the 1 must be inside the ()^3 .. i will write more in a new reply

4. OK .. i am using plain english as i have not yet figured out how to put the mathematical letters.

so write (k+1)^3 = k^3+1+3k^2+3k > 3^k +3k^2+3k

so if you prove that 3^(k+1)-3^k = 2.3^k > 3k^2 + 3k then you are through.

apply the same trick of starting with the polynomial. this time again you have to compare a polynimal of lesser degree with a exponential. go on till what remains is obvious. i hope i have made it clear. just write whatever i have told you on a piece of paper .. you will get it.

5. ok see this ... $(k+1)^3 = k^3 + 1 + 3k^2 + 3k < 3^k + 1 + 3k^2 + 3k$
you need to prove that $(k+1)^3 < 3^{k+1}$
take the difference of the two inequalities. it follows that you must prove $1 + 3k^2 + 3k < 2.3^k$.

now start afresh with this inequality using the same trick. this time you will get something like $6k+8 < 4.3^k$. again do the same step. ignore any mistakes that i may have done ... the essential point is that degree of the polynomial keeps reducing whereas the exponential stays same.

remember that each time your applicable $k$ has a different domain. so just keep track of it.

perhaps you may have recognized what i am essentially doing. i am replicating the way of taking derivatives in a continuous setup to the discrete setup that you need.

6. Frankly, that doesn't make a whole lot of sense to me, I'm so confused and I can't follow where you got the $2.3^k$ term from!
So, we know $3^k > k^3$ and $k \geq 4$, now we want to prove:

$3^{k+1} > (k+1)^3$

$
3.3^k > k^3+3k^2+3k+1
$

This is where I am so far. Any more explanation is appreciated.

7. maybe i will have to write in detail

i hope you have got his far .. $(k+1)^3 = k^3 + 1 + 3k^2 + 3k < 3^k + 1 + 3k^2 + 3k$

frm this u get $(k+1)^3 - 1 - 3k^2 - 3k < 3^k$ -- (1)
u need to prove $(k+1)^3 < 3^{k+1} = 3.3^k$ --- (2)

the difference [(2) - (1)] of the two inequalities is $
1 + 3k^2 + 3k < 3.3^k - 3^k = 2.3^k$
--- (3)

now observe that if (1) and (3) is true then (2) must be true.

so the thing to prove now is $1 + 3k^2 + 3k < 2.3^k$. forget about the earlier inequality and instead treat this as your problem. in mathamatical language we say the the problem has been reduced to a new problem

to prove this again form 3 inequalities like above .. you will get a new inequality which is even simpler. finally you will get something which is just obvious. just try it with a pen and paper.

edit :: when i say the inequality is simpler i mean the degree of the polynomial part is smaller, even if the expression is a bigger one the polynomial itself is simpler to analyze.