You know from the base case that . You also know that so that gives you
Here's the question:
Use induction to prove that for every integer , .
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 and let P(n) be the statement:
" , "
Since I can't use P(1) as the base case so I'll do P(4) in its stead:
Inductive step:
Suppose and P(k) is true. So
Now we consider P(k+1)
What else can be done here to prove the inequality?
any help is appreciated
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.
ok see this ...
you need to prove that
take the difference of the two inequalities. it follows that you must prove .
now start afresh with this inequality using the same trick. this time you will get something like . 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 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.
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 term from!
So, we know and , now we want to prove:
This is where I am so far. Any more explanation is appreciated.
maybe i will have to write in detail
i hope you have got his far ..
frm this u get -- (1)
u need to prove --- (2)
the difference [(2) - (1)] of the two inequalities is --- (3)
now observe that if (1) and (3) is true then (2) must be true.
so the thing to prove now is . 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.