hmmm the qn ask us to use induction... so no choice bah...
hmmm the qn ask us to use induction... so no choice bah...
Was Hume the one that said life is meaningless?
Wah.. reminds me off my engineering maths modules I used to take in NUS... somehow looking at this brings back nightmares...
mathematical induction's link with actual induction is quite loose. the only relation is in that if a gives b once, and it "extends into the future" (future of numbers in math though) then you'd actually get the kind of scientific inductive reasoning that i was talking about.
i think you're possibly talking about nietzsche, who's linked to nihilism (well, like what you say, that life is without meaning).. hume was a lot more cheery in many ways.
Ah I see Considering taking a module on that guy =p Dont want to turn emo after that...
< 2^k + 3k^2 + 3k +1 (1)
= 2^k + k^3 [3/k + 3/ (k^2) + 1/ (k^3)]
Now, for n >9, 3/k + 3/(k^2) + 1/ (k^3) <1 (2)
Hence, 2^k + k^3 > 2^k + k^3 [......] (3)
so (k+1)^3 +2 < 2^k + k^3 (4)
< 2^k + k^3 + 2
< 2^k + 2^k
< 2 ^ (k+1) (shown)
(1) Recall the assumption that k^3 + 2 < 2^k, thus
k^3 +2 + (3 k^2 + 3k +1) < 2^k + 3k^2 + 3k +1 (rearranging and substituting)
(2) line 2 is the coefficient of k^3 in the previous line. It is rearranged as such, since the inductive statement requires k^3.
Now, when k > 9, 3/k < 0.33 and the next 2 terms are smaller than the first term. Thus the sum of the 3 terms must be <1.
From (3), k^3 > k^3 ( 3/k + 3/ k^2 + 1/ k^3), since the terms in bracket is <1.
(4) (k+1)^3 +2 < 2^k + k^3 ( 3/k + 3/ k^2 + 1/ k^3) < 2^k + k^3
Hi AhSeng, the solution u provided is quite understandable... but theres a couple of parts i still dun get it (boxed in red)... hope u can explain it.
btw, Im really very touched and grateful for all the help here!
way to go, ahseng. my brain is as rusty as xxxx...
it's a good explanation, but unfortunately might not hold up as very credible in a math exam.
the best way to do it is simply to solve for 3k^2 + 3k + 3 = k^3 + 4, then show that LHS < RHS for k>9
either that or draw a graph, no doubt more tedious.
one thing i don't really understand though; if you actually bother doing either of the above mentioned, it turns out that as long as k>3.5 or so (thereabouts) then the inequality will be true. yet the statement ONLY works for k>9.
it's been a long time though, i can't remember if induction was quite THAT flawed. i mean, it was horrible and pointless to most of us then, but this is another thing.
Mathematics Induction is quite an important topic for computer science as many a time, we write software with lots of iterations. To ensure our iteration program works as devised, we sometimes need to prove the function work as what we expected and this can be proved by mathematics induction.
Mathematics induction shows that for every next term in the iteration, the formula gives the correct result. (e.g. when K = 8 , 9 ,10 ,...... infinity). Without which, it will be impossible to prove. e.g. k = 10^300 the next term k= 10^300+1. Your computer most probably couldn't give u the result for this value of k^3(too big to be computed) but by mathematics induction, it is proven that the equation remains true.
Last edited by AhSeng; 6th May 2008 at 07:56 PM. Reason: Included an extra paragraph
although i cant completely say i understand it 100%, but i get most of what u had explained.
thanks a lot for the help once again.
do u happen to be a lecturer or teacher?
u are good in teaching, even without face to face explanation!!
Welcome to the world of computer science. Induction is just a small topic in CS though.. Wait till you get to linear combination and equivalence relations that forms the basis of current world encryption/decryption like RSA and Diffie-Hellman key distribution scheme.
ahseng's solution is the closest ... i will refine and elaborate what ahseng has done ....
and elaborating the last part of ahseng's explanation which wasn't quite complete
To prove n^3+2 < 2^n for n>9
need to prove next case (k+1)
need to prove (k+1)^3+2 < 2^(k+1)
need to prove:
k^3+3k^2+3k+1+2 < 2*2^k
k^3+2 + (3k^2+3k+1) < 2*2^k ……. (1)
but we know from our assumption that k^3+2 < 2^k for n=k, or 2^k > k^3+2
Inequality (1) remains valid if we replace the right hand side by some expression bigger than 2*2^k
Since 2^k > k^3+2 hence k^3+2 + (3k^2+3k+1) < 2* (k^3+2)
Simplifying this results in -> k^3 + 1 > 3k^2 + 3k – this is what we need to prove
Since k^3 = k*(k^2) it follows that k^3 = k*(k^2) >9k^2 since k >9
k^3 > 9k^2
k^3 > 3k^2 + 6k*k
k^3 > 3k^2 + 54k since k>9
If k^3 > 3k^2 + 54k quite obviously k^3 > 3k^2 + 3k and even more obviously k^3 + 1 > 3k^2 + 3k
Case proven ...
a) There is one important part ahseng has not properly addressed - in inequality (1) above, ahseng has simply substituted 2^k with k^3+2 - this happened to be true because 2^k > k^3+2 as explained above and inequality (1) will only be true if 2^k > k^3+2 - if 2^k < k^3+2, then we could not substitute in - we need to be careful with the inequality signs
Actually, Ah Seng's solution is the same as mine, except I worked from LHS to RHS, but he worked on LHS and RHS at the same time. In working with inequalities, this can be quite dangerous. In his solution, it appears that he substituted k^3 +2 = 2^k when that is actually an inequality and thus is actually wrong. But this, he corrected in the next explanation.
Note: In the solution, you should not put 2(2^k) = 2(k^3 +2)! That is a mistake.
The only difference lies in that Ah Seng is satisfied to conclude that 3k^2 + 3k +1 < k^3, I find that somewhat sloppy in my solution. That's why I took an additional step to write 3k^2 + 3k +1 = k^3 (3/k + 3/k^2 + 1/ k^3) and prove that this coefficient is always less than 1 to demonstrate the inequality.
Otherwise, if you examine the two solution, or rewrite Ah Seng's solution from LHS to RHS, you'd find the two solution is identical.
If you dun see it, why don't you look at it this way. Once k=9 had been satisfied, you work on k=10 and rewrite the equation such the k=10 relies on k=9 to find the answers(basis of iterations in CS). This is where u catch the induction theory, proving the next case base on the previous case. If your mathematics workings does not prove the induction is based on the previous case, it isn't induction and you can't prove that the next case will be the same as the one before.