hmmm the qn ask us to use induction... so no choice bah...
hmmm the qn ask us to use induction... so no choice bah...
Photo Album - Photo Album
Haha I thought that's assumption based on extrapolation not induction cause induction assumes that each atomic step would result in a predefined amount of change based on the assumed true premise with no random or external influences. Dunno lah too much studying making me confused
Was Hume the one that said life is meaningless?
Furry Photos - Photography for the Modern Pet
Wah.. reminds me off my engineering maths modules I used to take in NUS... somehow looking at this brings back nightmares...
well actually i was just being frivolous
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.
Photo Album - Photo Album
Ah I see Considering taking a module on that guy =p Dont want to turn emo after that...
Furry Photos - Photography for the Modern Pet
(k+1)^3 + 2 = (k^3 + 3k^2 + 3k +1) +2
< 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!
Photo Album - Photo Album
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.
Normally, the question will only require you to prove the equation is true when it is just slightly bigger than the treshold but there is a fundamental basis for this question. The question is setup so that students understand why in induction proving, one will have to prove the base case is correct. If the question asked for +ve integer > 8, the base case is wrong when we try to show that n^3+2 is < 2^n, The induction still works out correct though and it will be wrong to say that the equation is true.
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!!
Photo Album - Photo Album
Nope, i am not a lecturer nor a teacher. Thanks for the compliments though.
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.
I think you don't see the whole point of induction if you say the above. The setup of this question does not require students to go a long way round to find the answers. In mathematics induction, once we defined the base case, and had proven the base case, the equation already warrants merit. The induction step is used to prove the k+1 term is also satisfying the equation. We can safely quote and use the base equation once it already satisfied the base case.
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.
We are just trying to prove that the equation is satisfied for all k>9 and is not interested in the final answers. It's my mistake for putting that = sign that misled you. I should have use implied => for it. I would have to defend my work if you find it sloppy. It isn't sloppy from my point of view as we are not trying to be precise here with this question. We are only interested in proving that equation is correct. Your method of finding the coefficients are very precise but it isn't really required as we are not trying to find the anwers where the equation becomes true. This isn't engineering maths where one tends to find the exact answers to k... my friend. In computers it's all 1s(true) or 0s(false) and in this question, we are simply just trying to find out if it is true for all K>9. Also, we tend to deal more in Integers than floating points in computer science. We can't possibly ask the computer to loop the program 10.5 times right?
Bookmarks