Cubes Sum Product Squares plus Induction Goodness
Moderator: Michael Wallace
- Matt Morrison
- Post-apocalypse
- Posts: 7822
- Joined: Wed Oct 22, 2008 2:27 pm
- Location: London
- Contact:
Cubes Sum Product Squares plus Induction Goodness
On one of the episodes of this week's Poker After Dark (not relevant but giving some circumstantial information)
they were talking about the problem of trying to prove that:
the sum of cubes 1-n will always be its product squared
(and for what it is worth, they also stated that it is harder to prove geometrically than algebraically)
1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36 ... and ... (1 + 2 + 3) ^2 = 6^2 = 36
1^3 + 2^3 + 3^3 + 4^3 + 5^3 = 1 + 8 + 27 + 64 + 125 = 225 ... and ... (1 + 2 + 3 + 4 + 5) ^2 = 15^2 = 225
I have little to add other than I know you guys were enjoying the coin maths problem, thought you might like something else to work on.
I fear my days of maths are too far behind me to add anything more technically interesting.
they were talking about the problem of trying to prove that:
the sum of cubes 1-n will always be its product squared
(and for what it is worth, they also stated that it is harder to prove geometrically than algebraically)
1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36 ... and ... (1 + 2 + 3) ^2 = 6^2 = 36
1^3 + 2^3 + 3^3 + 4^3 + 5^3 = 1 + 8 + 27 + 64 + 125 = 225 ... and ... (1 + 2 + 3 + 4 + 5) ^2 = 15^2 = 225
I have little to add other than I know you guys were enjoying the coin maths problem, thought you might like something else to work on.
I fear my days of maths are too far behind me to add anything more technically interesting.
Last edited by Gary Male on Sun Feb 15, 2009 8:02 pm, edited 1 time in total.
Reason: Title now includes what this topic is now about
Reason: Title now includes what this topic is now about
- Michael Wallace
- Racoonteur
- Posts: 5458
- Joined: Mon Jan 21, 2008 5:01 am
- Location: London
Re: Cubes Sum Product Squares
I can't actually be bothered to do it again, but it's (very) easy to prove the sum of the first n integers is 1/2 * n * (n+1) (either by induction or just drawing dots and making rectangles), and you can do it for cubes by induction (that I do remember doing at A level). There may be neater ways but that's how I'd do it.
-
- Series 59 Champion
- Posts: 574
- Joined: Sat Jul 19, 2008 4:26 pm
Re: Cubes Sum Product Squares
Agreed. Induction lacks a certain elegance, but gets the job done. Geometric methods tend to be nicer, but at the expense of being more difficult. In this case, I'd content myself with simple induction.Michael Wallace wrote:I can't actually be bothered to do it again, but it's (very) easy to prove the sum of the first n integers is 1/2 * n * (n+1) (either by induction or just drawing dots and making rectangles), and you can do it for cubes by induction (that I do remember doing at A level). There may be neater ways but that's how I'd do it.
- Ian Volante
- Postmaster General
- Posts: 3974
- Joined: Wed Sep 03, 2008 8:15 pm
- Location: Edinburgh
- Contact:
Re: Cubes Sum Product Squares
I'm sort of glad I never did further maths, although it might have helped with some of the more nebulous aspects of my astrophysics degree.
No-one's ever told me what induction is, although I suspect it's simply solving equations algebraically?
Didya see what I did there?
No-one's ever told me what induction is, although I suspect it's simply solving equations algebraically?
Didya see what I did there?
meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles
-
- Series 59 Champion
- Posts: 574
- Joined: Sat Jul 19, 2008 4:26 pm
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
One of a few bits of maths I really hate, can't really get my head round and don't fully believe as I feel like you're being tricked.Junaid Mubeen wrote:http://en.wikipedia.org/wiki/Mathematical_induction
3 is prime. Add 2. 5 is prime. Add 2. 7 is prime. Therefore all odd numbers are primes.
- Michael Wallace
- Racoonteur
- Posts: 5458
- Joined: Mon Jan 21, 2008 5:01 am
- Location: London
Re: Cubes Sum Product Squares
But that's not induction. All induction says is that if you can reach the first rung of a ladder, and that if you know that from any rung of the ladder you can reach the next rung, then you can climb the whole ladder - all you've done there is shown that you can climb the first 3 rungs. (Although I appreciate you've probably had this explained at you time and time again, so I can understand if it's just 'one of those things'.)Kirk Bevins wrote:One of a few bits of maths I really hate, can't really get my head round and don't fully believe as I feel like you're being tricked.Junaid Mubeen wrote:http://en.wikipedia.org/wiki/Mathematical_induction
3 is prime. Add 2. 5 is prime. Add 2. 7 is prime. Therefore all odd numbers are primes.
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
I looked at that webpage and it made me angry that in their "proof" they substituted in an expression that they were trying to prove. Surely you can't do this? It makes me so angry because I swear this isn't mathematically/logically sound.
Re: Cubes Sum Product Squares
Kirk Bevins wrote:
One of a few bits of maths I really hate, can't really get my head round and don't fully believe as I feel like you're being tricked.
3 is prime. Add 2. 5 is prime. Add 2. 7 is prime. Therefore all odd numbers are primes.
Did you know that any interger greater then three can be expressed as the sum of 2 pirmes, and any interger greater then 5 can be expressed as the sum of 3 primes?
I dont think this has ever been proved. Its true by lack of counter example I think.
- Kai Laddiman
- Fanatic
- Posts: 2314
- Joined: Wed Oct 15, 2008 3:37 pm
- Location: My bedroom
Re: Cubes Sum Product Squares
Just a little question - shouldn't it be the sum of the numbers squared?Matt Morrison wrote:the sum of cubes 1-n will always be its product squared
16/10/2007 - Episode 4460
Dinos Sfyris 76 - 78 Dorian Lidell
Proof that even idiots can get well and truly mainwheeled.
Dinos Sfyris 76 - 78 Dorian Lidell
Proof that even idiots can get well and truly mainwheeled.
Re: Cubes Sum Product Squares
I hate to be picky, but did you mean: The sum of cubes 1 to n will always be the same as the sum of (1 to n)^2Matt Morrison wrote: the sum of cubes 1-n will always be its product squared
I just did a chapter on this sort of stuff in further pure 1.
The sum of the cubes of the first n natural numbers is (n^2(n+1)^2)/4
The sum of the first n Natural numbers is n/2(n+1)
Given that, we can work out the square of the sum of the first n natural numbers to be n/2(n+1) squared.
(n/2(n+1))(n/2(n+1))=(n^2(n+1)^2)/4, which is the same as the formula for the sum of the first n cube numbers
This isnt a proof, i just wanted to apply what i have recently learned to see if it worked, and it does
- Michael Wallace
- Racoonteur
- Posts: 5458
- Joined: Mon Jan 21, 2008 5:01 am
- Location: London
Re: Cubes Sum Product Squares
That's not how maths worksJackHurst wrote:I dont think this has ever been proved. Its true by lack of counter example I think.
Edit: Also this.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
I'm pretty sure someone would've noticed by now if induction were unsound. I hope you find the argument from authority more persuasive than the argument from logic.Kirk Bevins wrote:I looked at that webpage and it made me angry that in their "proof" they substituted in an expression that they were trying to prove. Surely you can't do this? It makes me so angry because I swear this isn't mathematically/logically sound.
-
- Series 59 Champion
- Posts: 574
- Joined: Sat Jul 19, 2008 4:26 pm
Re: Cubes Sum Product Squares
The absence of a known counterexample doesn't mean one doesn't exist.JackHurst wrote: Its true by lack of counter example I think.
http://en.wikipedia.org/wiki/P%C3%B3lya_conjecture
-
- Series 59 Champion
- Posts: 574
- Joined: Sat Jul 19, 2008 4:26 pm
Re: Cubes Sum Product Squares
Quite.Kai Laddiman wrote:Just a little question - shouldn't it be the sum of the numbers squared?Matt Morrison wrote:the sum of cubes 1-n will always be its product squared
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
Not really - there could be loads of people like me that don't quite follow it but just accept it.Charlie Reams wrote: I'm pretty sure someone would've noticed by now if induction were unsound. I hope you find the argument from authority more persuasive than the argument from logic.
Never accept authority unless you understand it yourself. I was 10 years old when I got an answer to a probability question as 64. My teacher said 32 and I kept arguing that it was 64. The rest of the class told me to shut up because I was arguing with an experienced teacher but the stubbornness of me kicked in and I knew I was right so I pursued. Eventually the teacher saw the error of her ways and corrected herself and gave me 5 house points at the same time. This was an early lesson in life never to trust people who you think may be in the know (e.g. although I can confidently do GCSE maths I've made a couple of errors when teaching it before now, much to be annoyance, but it took a couple of clever girls to correct me and I realised I just wasn't concentrating hard enough.)
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
A noble sentiment no doubt, but there's a difference between not accepting something and rejecting it. I don't understand general relativity but I don't argue that it must be some kind of trick.Kirk Bevins wrote:Not really - there could be loads of people like me that don't quite follow it but just accept it.Charlie Reams wrote: I'm pretty sure someone would've noticed by now if induction were unsound. I hope you find the argument from authority more persuasive than the argument from logic.
Never accept authority unless you understand it yourself. I was 10 years old when I got an answer to a probability question as 64. My teacher said 32 and I kept arguing that it was 64. The rest of the class told me to shut up because I was arguing with an experienced teacher but the stubbornness of me kicked in and I knew I was right so I pursued. Eventually the teacher saw the error of her ways and corrected herself and gave me 5 house points at the same time. This was an early lesson in life never to trust people who you think may be in the know (e.g. although I can confidently do GCSE maths I've made a couple of errors when teaching it before now, much to be annoyance, but it took a couple of clever girls to correct me and I realised I just wasn't concentrating hard enough.)
I invite you to find something which can be "proved" by induction but is actually false. Otherwise you're coming straight from the Richard Brittain School of Discussion.
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
I'm sure it does make perfect sense but I don't understand it and it doesn't make logical sense in my brain which pisses me off mightily.Charlie Reams wrote:
I invite you to find something which can be "proved" by induction but is actually false. Otherwise you're coming straight from the Richard Brittain School of Discussion.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
I think Raccoon gave a pretty good intuition for it.Kirk Bevins wrote:I'm sure it does make perfect sense but I don't understand it and it doesn't make logical sense in my brain which pisses me off mightily.Charlie Reams wrote:
I invite you to find something which can be "proved" by induction but is actually false. Otherwise you're coming straight from the Richard Brittain School of Discussion.
- Phil Reynolds
- Postmaster General
- Posts: 3329
- Joined: Fri Oct 31, 2008 3:43 pm
- Location: Leamington Spa, UK
Re: Cubes Sum Product Squares
What exactly is it about it that doesn't make logical sense to you? If you can prove by simple algebra that if a statement is true for any natural number n then it is also true for n+1, surely logic dictates that you only have to find one example of n for which the statement is true and immediately you know that it's also true for all natural numbers greater than n?Kirk Bevins wrote:I'm sure it does make perfect sense but I don't understand it and it doesn't make logical sense in my brain which pisses me off mightily.
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
If you can prove by simple algebra that if a statement is true for any natural number n then why bother proving it for n+1?Phil Reynolds wrote:What exactly is it about it that doesn't make logical sense to you? If you can prove by simple algebra that if a statement is true for any natural number n then it is also true for n+1Kirk Bevins wrote:I'm sure it does make perfect sense but I don't understand it and it doesn't make logical sense in my brain which pisses me off mightily.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
That's not how it works. You start by assuming it for arbitrary n and use that to prove it for n+1. I'm totally lost as to how you finished a degree in maths without knowing the mechanics of proof by induction, never mind whether you actually understand it.Kirk Bevins wrote:If you can prove by simple algebra that if a statement is true for any natural number n then why bother proving it for n+1?Phil Reynolds wrote:What exactly is it about it that doesn't make logical sense to you? If you can prove by simple algebra that if a statement is true for any natural number n then it is also true for n+1Kirk Bevins wrote:I'm sure it does make perfect sense but I don't understand it and it doesn't make logical sense in my brain which pisses me off mightily.
- Phil Reynolds
- Postmaster General
- Posts: 3329
- Joined: Fri Oct 31, 2008 3:43 pm
- Location: Leamington Spa, UK
Re: Cubes Sum Product Squares
Your reply doesn't even make grammatical sense in English! The point (at least initially) is not to prove that a statement is true for any n. It's to prove that if it's true for any n, then it's also true for n+1.Kirk Bevins wrote:If you can prove by simple algebra that if a statement is true for any natural number n then why bother proving it for n+1?
Re: Cubes Sum Product Squares
Sorry to derail the thread in this manner, but so I get it clear would induction be used as a way to prove that for any positive integer n, n^2 is positive? As in where n=1 , n^2 = 1^2 = 1 is positive, (n+1)^2 = n^2 + 2n + 1 = 4 is positive? Or am I off the mark here?Charlie Reams wrote:
That's not how it works. You start by assuming it for arbitrary n and use that to prove it for n+1. I'm totally lost as to how you finished a degree in maths without knowing the mechanics of proof by induction, never mind whether you actually understand it.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
Here's an induction proof that n² is positive. Hopefully the simplicity of the problem makes it easier to understand the method.Gary Male wrote:Sorry to derail the thread in this manner, but so I get it clear would induction be used as a way to prove that for any positive integer n, n^2 is positive? As in where n=1 , n^2 = 1^2 = 1 is positive, (n+1)^2 = n^2 + 2n + 1 = 4 is positive? Or am I off the mark here?Charlie Reams wrote:
That's not how it works. You start by assuming it for arbitrary n and use that to prove it for n+1. I'm totally lost as to how you finished a degree in maths without knowing the mechanics of proof by induction, never mind whether you actually understand it.
Base case: Is 1² positive? Yes. (The base case is usually trivial.)
Inductive case: Take some arbitrary positive number k. Assume for the moment k² is positive. From this, can we conclude that (k+1)² is also positive? Yes, because (k+1)² = k² + 2k + 1; we assumed already that k² is positive, and 2k+1 is also positive if k is positive (hopefully obvious), and adding the two positive numbers k² and 2k+1 also gives a positive number (hopefully also obvious.) Hence if k² is positive then (k+1)² is also positive.
So, the base case gets us on the first rung of the ladder, and the inductive case shows us how to get from any given rung to the next rung. This completes the proof.
To look at it another way: if you pick any number n and ask me "is n² positive?", it's trivial to construct a proof that it is; start with 1² being positive, then use the inductive case to prove 2² is positive, and so on all the way up to n².
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
Charlie Reams wrote: That's not how it works. You start by assuming it for arbitrary n and use that to prove it for n+1. I'm totally lost as to how you finished a degree in maths without knowing the mechanics of proof by induction, never mind whether you actually understand it.
Haha they always had questions like "show, by induction..." and I always left those out. Shows why I only got a 2:1.
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
I just copied your sentence so yours must have been just as bad!Phil Reynolds wrote:Your reply doesn't even make grammatical sense in English!Kirk Bevins wrote:If you can prove by simple algebra that if a statement is true for any natural number n then why bother proving it for n+1?
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
I'm not happy with this as 0 squared is not positive.Charlie Reams wrote: Here's an induction proof that n² is positive. Hopefully the simplicity of the problem makes it easier to understand the method.
Base case: Is 1² positive? Yes. (The base case is usually trivial.)
Inductive case: Take some arbitrary positive number k. Assume for the moment k² is positive. From this, can we conclude that (k+1)² is also positive? Yes, because (k+1)² = k² + 2k + 1; we assumed already that k² is positive, and 2k+1 is also positive if k is positive (hopefully obvious), and adding the two positive numbers k² and 2k+1 also gives a positive number (hopefully also obvious.) Hence if k² is positive then (k+1)² is also positive.
So, the base case gets us on the first rung of the ladder, and the inductive case shows us how to get from any given rung to the next rung. This completes the proof.
To look at it another way: if you pick any number n and ask me "is n² positive?", it's trivial to construct a proof that it is; start with 1² being positive, then use the inductive case to prove 2² is positive, and so on all the way up to n².
Right, now prove to me that n(n+1) is always positive. Start with n=1 and you have problems again.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
I was taking positive as meaning 1 or larger. I realise this definition is debatable, but it's also irrelevant: either 0 is positive, in which case 0² is positive, or 0 is not positive in which case the conjecture doesn't claim to say anything about it.Kirk Bevins wrote: I'm not happy with this as 0 squared is not positive.
I have no idea what
is about, sorry.Right, now prove to me that n(n+1) is always positive. Start with n=1 and you have problems again.
- Phil Reynolds
- Postmaster General
- Posts: 3329
- Joined: Fri Oct 31, 2008 3:43 pm
- Location: Leamington Spa, UK
Re: Cubes Sum Product Squares
No, you copied half my sentence and then added something of your own onto the end of it. Trouble was, the half of my sentence you copied didn't make grammatical sense without the other half - which kind of gave away the fact that you hadn't read it properly.Kirk Bevins wrote:I just copied your sentence so yours must have been just as bad!Phil Reynolds wrote:Your reply doesn't even make grammatical sense in English!
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
Phil, this really makes no sense, please try to use full sentences in future.Phil Reynolds wrote:you copied half my and then trouble was half of my sentence you sense without the other fact that you hadn'properly.
- Michael Wallace
- Racoonteur
- Posts: 5458
- Joined: Mon Jan 21, 2008 5:01 am
- Location: London
Re: Cubes Sum Product Squares
Well you haven't stated the problem precisely, but I'm going to assume you mean "Show that n(n+1) is always positive for n a positive integer".Kirk Bevins wrote:Right, now prove to me that n(n+1) is always positive. Start with n=1 and you have problems again.
1. n =1, n(n+1) = 1*2 = 2 >0 so that's fine.
2. Suppose k(k+1) is positive, is (k+1)(k+1+1) positive?
(k+1)(k+2) = k² + 3k + 2 = (k² + k) + 2k + 2 = k(k+1) + 2(k+1).
We know that k(k+1) > 0, and 2(k+1) is obviously greater than 0 because k is. So we've shown that if k(k+1) is positive, then (k+1)((k+1)+1) is positive.
This isn't a great example though, because it's obviously true just, well, because it's obvious (because positive * positive is positive). I'm not sure where your "problems" come from.
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
No we don't!!!! This is what we are trying to prove. This is my problem.Michael Wallace wrote:
We know that k(k+1) > 0,
- Michael Wallace
- Racoonteur
- Posts: 5458
- Joined: Mon Jan 21, 2008 5:01 am
- Location: London
Re: Cubes Sum Product Squares
We do though, because earlier on we've supposed it to be true. We are only supposing it is true temporarily within this second step to show that if it is true for n = k, then it is true for n = k + 1.Kirk Bevins wrote:No we don't!!!! This is what we are trying to prove. This is my problem.Michael Wallace wrote:
We know that k(k+1) > 0,
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
You can't suppose something is true if you've not proved it! I suppose the sky is yellow and if I mix it with blue paint I get green. Yellow and blue make green so therefore my assumption of the sky being yellow must be true. This is the logic I see in this.Michael Wallace wrote:We do though, because earlier on we've supposed it to be true. We are only supposing it is true temporarily within this second step to show that if it is true for n = k, then it is true for n = k + 1.Kirk Bevins wrote:No we don't!!!! This is what we are trying to prove. This is my problem.Michael Wallace wrote:
We know that k(k+1) > 0,
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
Yes you can. You can suppose anything you like. Whether your conclusion is true will depend on whether your supposition is true, but there's nothing wrong with making some assumption and then seeing where it gets you.Kirk Bevins wrote:You can't suppose something is true if you've not proved it!
Consider this classical argument, which I hope you accept:
Fido is a dog.
If an animal is a dog, then it's a mammal.
Hence, Fido is a mammal.
Notice in line 2 we made an assumption (that the animal is a dog.) This doesn't mean we're assuming anything about all animals. It means only that, if the animal is a dog then we can draw some conclusion about it. We make this assumption temporarily as part of a wider proof.
- Phil Reynolds
- Postmaster General
- Posts: 3329
- Joined: Fri Oct 31, 2008 3:43 pm
- Location: Leamington Spa, UK
Re: Cubes Sum Product Squares
No it isn't. What we are trying to prove is that, if the expression is true for k, then it's also true for k+1. There's a difference.Kirk Bevins wrote:No we don't!!!! This is what we are trying to prove.Michael Wallace wrote: We know that k(k+1) > 0,
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
No. My original question was "Prove that n(n+1) is positive".Phil Reynolds wrote: No it isn't. What we are trying to prove is that, if the expression is true for k, then it's also true for k+1. There's a difference.
Re: Cubes Sum Product Squares
I'll try a layman's explanation anyway. A continuous probability distribution is represented by a graph of a function that is always positive, and the area underneath the graph is 1.....Kirk Bevins wrote:No. My original question was "Prove that n(n+1) is positive".Phil Reynolds wrote: No it isn't. What we are trying to prove is that, if the expression is true for k, then it's also true for k+1. There's a difference.
Re: Cubes Sum Product Squares
Let me have a stab at this. induction proofs are sneaky as your goal is not to prove a statement directly, but rather to prove an implication of the form: if the statement is true for n, then it is also true for n+1. This requires the assumption that the statement is true for n, but no circular reasoning is involved as at this point all you have proved is the implication. It is quite possible for the implication to be true and the statement to be false for all n.Kirk Bevins wrote:No. My original question was "Prove that n(n+1) is positive".Phil Reynolds wrote: No it isn't. What we are trying to prove is that, if the expression is true for k, then it's also true for k+1. There's a difference.
To actually prove the statement, we need a basis case. So say we can show (usually by direct calculation) that the statement is true for n=1. Now, we've previously proved the implication that if a statement is true for n, then its true for n+1. As our statement is true for 1, its also true for 2, via the implication. But now we can apply the implication again: as the statement as true for 2, its true for 3, and as its true for 3, its true for 4, and so on.
Transferring this to a physical setting, you would surely accept an argument like, "if the sun goes supernova, then we're all going to die". and not dismiss this as circular reasoning because the sun hasn't actually gone nova yet. The implication is still undeniably true.
In an induction proof, we
1)Prove an implication by assuming the statement is true. We haven't proved the statement itself yet, but the implication is undeniably true.
2)Combine the implication with a basis case, and apply the undeniably true implication an infinite number of times (ie its true for 1 so its true for 2, its true for 2 so its true for 3, etc) to show the statement is true for all numbers greater than the basis.
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
I liked all that post, Paul, except this bit. How can you "assume" the statement is true when it may not be. I cringe every time I hear the word "assume" and scream.Paul Howe wrote: In an induction proof, we
1)Prove an implication by assuming the statement is true.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
I think you just don't understand the purpose of assumptions. Here's the same argument again:Kirk Bevins wrote:I liked all that post, Paul, except this bit. How can you "assume" the statement is true when it may not be. I cringe every time I hear the word "assume" and scream.Paul Howe wrote: In an induction proof, we
1)Prove an implication by assuming the statement is true.
Fido is a dog.
Assume an animal is a dog. Then, it's a mammal.
Hence, Fido is a mammal.
Of course animals are not in general dogs, so our assumption may not be true. However this doesn't affect the solidity of the argument, which is only concerned with the case in which the animal is a dog.
Re: Cubes Sum Product Squares
Because you're trying to establish an implication. An implication says if x is true, then y happens. That x could easily be false. In my physical example, the statement "the sun has gone supernova" is false, but the implication "if the sun goes nova, then all human life will be destroyed" is still true.Kirk Bevins wrote:I liked all that post, Paul, except this bit. How can you "assume" the statement is true when it may not be. I cringe every time I hear the word "assume" and scream.Paul Howe wrote: In an induction proof, we
1)Prove an implication by assuming the statement is true.
Also, what Charlie said.
Oh, and do you understand how proof by contradiction works? There we show something is false by assuming its true and deriving a logical absurdity. If you can get your head round that you're well on the way to grasping induction.
Last edited by Paul Howe on Sun Feb 15, 2009 9:14 pm, edited 1 time in total.
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares
I don't understand what Charlie said. The middle sentence about "assume an animal is a dog" is confusing.Paul Howe wrote: Also, what Charlie said.
-
- Post-apocalypse
- Posts: 13382
- Joined: Mon Jan 21, 2008 10:37 pm
Re: Cubes Sum Product Squares plus Induction Goodness
I'm going to have a try. If enough of us do this with slightly different wording, we'll get there! And I'll avoid the word "assume"!
So you want to find out if a property if true for all integers.
1. You find a proof that shows for all x that the property holds for it also holds for x + 1. (Actually, this proof might involve using the word "assume".)
2. You prove that the property holds for x = 1.
Job done.
So you want to find out if a property if true for all integers.
1. You find a proof that shows for all x that the property holds for it also holds for x + 1. (Actually, this proof might involve using the word "assume".)
2. You prove that the property holds for x = 1.
Job done.
- Ian Volante
- Postmaster General
- Posts: 3974
- Joined: Wed Sep 03, 2008 8:15 pm
- Location: Edinburgh
- Contact:
Re: Cubes Sum Product Squares plus Induction Goodness
You assume.Gavin Chipper wrote:Job done.
meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares plus Induction Goodness
You should say probably say something like "some arbitrary x" rather than "all x".Gavin Chipper wrote: 1. You find a proof that shows for all x that the property holds for it also holds for x + 1. (Actually, this proof might involve using the word "assume".)
- Phil Reynolds
- Postmaster General
- Posts: 3329
- Joined: Fri Oct 31, 2008 3:43 pm
- Location: Leamington Spa, UK
Re: Cubes Sum Product Squares
Kirk might like to ponder that without this fundamental principle, upon which the "Bombes" at Bletchley Park were based, the Allies would have been unable to crack the Enigma code and we would in all likelihood have lost the war...Paul Howe wrote:Because you're trying to establish an implication. An implication says if x is true, then y happens. That x could easily be false.Kirk Bevins wrote:How can you "assume" the statement is true when it may not be.Paul Howe wrote: In an induction proof, we
1)Prove an implication by assuming the statement is true.
Re: Cubes Sum Product Squares
I think - and I only did A-level maths, and it was long ago, so I'm in way over my head here - that the problem Kirk has is that he isn't satisfied that you can reach the next rung from any rung. IF that's true, then yes of course you can climb the ladder. But THAT is what he wants proving.Michael Wallace wrote: All induction says is that if you can reach the first rung of a ladder, and that if you know that from any rung of the ladder you can reach the next rung, then you can climb the whole ladder - all you've done there is shown that you can climb the first 3 rungs.
How about this?
Fido is a dog. Fido is an animal.
Dogs are mammals.
Animals are mammals ONLY IF they are also dogs.
Therefore, Fido is a mammal.
Polly is a parrot. Polly is an animal. Felix is a cat. Felix is an animal.
Parrots are not dogs. Cats are not dogs.
Animals are mammals ONLY IF they are also dogs.
Therefore Felix and Polly are not mammals.
Of course, the assumption is not actually true (unless you remove the word only). So the proof that Felix is not a mammal is flawed. And I believe that is where the problem lies. Kirk wants the assumption to be proved before he'll accept the results.
"If the sun goes supernova, all human life will be destroyed." Not necessarily true. We might head out to other solar systems before it happens. The problem isn't with the statement, it's with the assumption.
Is that right, Kirk?
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares plus Induction Goodness
I don't think that's Kirk's problem. "If" and "only if" have completely different meanings.
Re: Cubes Sum Product Squares
Fine, if the sun goes supernova tomorrow, all human life will be destroyed. The point I was making, that you have to assume something to construct an implication, regardless of whether that something is true, is still clear.Nicky wrote:"If the sun goes supernova, all human life will be destroyed." Not necessarily true. We might head out to other solar systems before it happens.Michael Wallace wrote: All induction says is that if you can reach the first rung of a ladder, and that if you know that from any rung of the ladder you can reach the next rung, then you can climb the whole ladder - all you've done there is shown that you can climb the first 3 rungs.
No, you're going to confuse the poor boy even more! There's nothing wrong with the assuming the sun going nova, just that the conclusion of all human life being destroyed doesn't withstand the pedantry test. It's very difficult to construct an implication in the physical world that doesn't fail in some highly improbable circumstances, but I think its still useful to give concrete examples that help people reason in more abstract settings, even if we don't have the guarantee of absolute truth provided by an axiomatic foundation.Nicky wrote:
The problem isn't with the statement, it's with the assumption.
Re: Cubes Sum Product Squares plus Induction Goodness
Well, I do. Over to you, Kirk.Charlie Reams wrote:I don't think that's Kirk's problem.
I know that, I said that. I was just trying to show that just because you sometimes get the correct answer when you've made an assumption (as you do with Fido and Polly, using the 'only if' assumption) doesn't make the assumption correct, or mean all the answers it produces are correct (like Felix). Which I know you know.Charlie Reams wrote: "If" and "only if" have completely different meanings.
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares plus Induction Goodness
I have a few problems with it but the main one is as Nicky says - the assumption. I want it proving. I don't like you saying "assume x is true bla bla bla, oh look, here is a result" - I want you to show me that x is true, not just assume it. Secondly, you assume something and then use it in your proof (or you have to show that a dog is a mammal and then you use THAT in your proof which surely is bad logic as you haven't proved it yet). The n(n+1) was a good one as someone used the fact that it was always positive for positive n in their intermediate steps yet we haven't proved it yet!
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares plus Induction Goodness
That's not really what Nicky said, but anyway.
Consider the following argument (which is not an induction argument): "If all dogs are black then my dog is black." I take it you agree with this statement. One way to prove the statement would be:
1) Assume all dogs are black.
2) Consider my dog. Is he black? By assumption 1, yes.
3) Hence the overall statement "If all dogs are black then my dog is black" is true.
Notice that you agree with the whole statement even though you presumably don't agree with the assumption.
The point of the inductive step is not to establish directly that something holds for all x. It is to establish that, if it holds for any given x then it also holds for x+1. "But what if it doesn't hold for x?", you say. Well, what x would this be? It can't be x=1, because that's the base case which you checked explicitly. It can't be x=2, because by the inductive step, we know that if the statement is true for x=1 (which it is) then it's true for x=2 too. Likewise it can't be x=3, 4, etc... So there can be no case in which the statement doesn't hold; or, to put it another way, the statement holds in all cases. Which is what we were trying to prove.
Incidentally I think you'd have an easier time understanding this if your attitude was "I don't understand this but I would like to" rather than "I don't understand this so it must be wrong."
Consider the following argument (which is not an induction argument): "If all dogs are black then my dog is black." I take it you agree with this statement. One way to prove the statement would be:
1) Assume all dogs are black.
2) Consider my dog. Is he black? By assumption 1, yes.
3) Hence the overall statement "If all dogs are black then my dog is black" is true.
Notice that you agree with the whole statement even though you presumably don't agree with the assumption.
The point of the inductive step is not to establish directly that something holds for all x. It is to establish that, if it holds for any given x then it also holds for x+1. "But what if it doesn't hold for x?", you say. Well, what x would this be? It can't be x=1, because that's the base case which you checked explicitly. It can't be x=2, because by the inductive step, we know that if the statement is true for x=1 (which it is) then it's true for x=2 too. Likewise it can't be x=3, 4, etc... So there can be no case in which the statement doesn't hold; or, to put it another way, the statement holds in all cases. Which is what we were trying to prove.
Incidentally I think you'd have an easier time understanding this if your attitude was "I don't understand this but I would like to" rather than "I don't understand this so it must be wrong."
Re: Cubes Sum Product Squares
Aha. What we have here is a semantic misunderstanding.Paul Howe wrote:
Fine, if the sun goes supernova tomorrow, all human life will be destroyed. The point I was making, that you have to assume something to construct an implication, regardless of whether that something is true, is still clear.No, you're going to confuse the poor boy even more! There's nothing wrong with the assuming the sun going nova, just that the conclusion of all human life being destroyed doesn't withstand the pedantry test. It's very difficult to construct an implication in the physical world that doesn't fail in some highly improbable circumstances, but I think its still useful to give concrete examples that help people reason in more abstract settings, even if we don't have the guarantee of absolute truth provided by an axiomatic foundation.Nicky wrote:
The problem isn't with the statement, it's with the assumption.
"If the sun goes supernova, all human life will be destroyed". To you this is assumption, implication. To me it is statement, assumption.
Let me rephrase. The problem isn't with the assumption, it's with the implication. Pedantic or not, your implication was incorrect. Mathematically, you HAVE to be pedantic.
1 If a, then b
2 If b, then c
therefore
3 If a then c.
You can't say "Assume statement 1. Here is proof of statement 2. I've proved statement 3." You have to prove both statements, or your proof only holds in those circumstances where statement 1 is true.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cubes Sum Product Squares
Paul didn't say anything like that. He was just giving an example of a real-life statement of the form "if A then B" which anyone would agree with (pedantry notwithstanding) without agreeing that A is actually true. It's basically impossible to come up with an implication of this kind which is watertight in the real world (see the qualification problem) and that doesn't affect his point in the slightest, which was didactic, not mathematical.Nicky wrote:Aha. What we have here is a semantic misunderstanding.
"If the sun goes supernova, all human life will be destroyed". To you this is assumption, implication. To me it is statement, assumption.
Let me rephrase. The problem isn't with the assumption, it's with the implication. Pedantic or not, your implication was incorrect. Mathematically, you HAVE to be pedantic.
1 If a, then b
2 If b, then c
therefore
3 If a then c.
You can't say "Assume statement 1. Here is proof of statement 2. I've proved statement 3." You have to prove both statements, or your proof only holds in those circumstances where statement 1 is true.
-
- Kiloposter
- Posts: 1272
- Joined: Wed Jan 30, 2008 9:57 pm
Re: Cubes Sum Product Squares plus Induction Goodness
Assuming this isn't deliberate obtuseness.
You can show that 1000000^2 is positive if 999999^2 is positive, and it is if 999998^2 is positive. Several hours later you will have found that 1000000^2 is positive if 1^2 is positive. And it is. Nothing relies on an unproved assumption.
You can show that 1000000^2 is positive if 999999^2 is positive, and it is if 999998^2 is positive. Several hours later you will have found that 1000000^2 is positive if 1^2 is positive. And it is. Nothing relies on an unproved assumption.
Re: Cubes Sum Product Squares plus Induction Goodness
Isn't it? It's what I meant to say.Charlie Reams wrote:That's not really what Nicky said, but anyway.
So you are only TRYING to prove things in the circumstances where statement 1 is true?Nicky wrote:
1 If a, then b
2 If b, then c
therefore
3 If a then c.
You can't say "Assume statement 1. Here is proof of statement 2. I've proved statement 3." You have to prove both statements, or your proof only holds in those circumstances where statement 1 is true.
Re: Cubes Sum Product Squares plus Induction Goodness
Anyone mind if I clarify things for myself?Kirk Bevins wrote:I have a few problems with it but the main one is as Nicky says - the assumption. I want it proving. I don't like you saying "assume x is true bla bla bla, oh look, here is a result" - I want you to show me that x is true, not just assume it. Secondly, you assume something and then use it in your proof (or you have to show that a dog is a mammal and then you use THAT in your proof which surely is bad logic as you haven't proved it yet). The n(n+1) was a good one as someone used the fact that it was always positive for positive n in their intermediate steps yet we haven't proved it yet!
On the assumptions, I'm not seeing them as a problem for the reason Paul gave earlier. Take the "Suppose k(k+1) is positive, is (k+1)(k+1+1) positive?" part. It was shown that if k(k+1) is positive, then (k+1)((k+1)+1) is positive. If we plug some numbers in then we can see that working backwards to the base case "n =1, n(n+1) = 1*2 = 2 >0" proves everything. If (for example) 4(4+1) is positive, then so is (4+1)((4+1)+1) (or 5(5+1)). Working back, if 3(3+1) is positive then so is (3+1)((3+1)+1) (or 4(4+1) from the previous assumption) and so on down to if 1(1+1) is positive then so is (1+1)((1+1)+1) (or (2(2+1)). But from the base case we know 1(1+1) is positive, therefore so is (2(2+1), (3(3+1) and so on.
Am I right?
- Kirk Bevins
- God
- Posts: 4923
- Joined: Mon Jan 21, 2008 5:18 pm
- Location: York, UK
Re: Cubes Sum Product Squares plus Induction Goodness
Yeah that's their argument. I don't like the "suppose" bit.Gary Male wrote: On the assumptions, I'm not seeing them as a problem for the reason Paul gave earlier. Take the "Suppose k(k+1) is positive, is (k+1)(k+1+1) positive?" part. It was shown that if k(k+1) is positive, then (k+1)((k+1)+1) is positive. If we plug some numbers in then we can see that working backwards to the base case "n =1, n(n+1) = 1*2 = 2 >0" proves everything. If (for example) 4(4+1) is positive, then so is (4+1)((4+1)+1) (or 5(5+1)). Working back, if 3(3+1) is positive then so is (3+1)((3+1)+1) (or 4(4+1) from the previous assumption) and so on down to if 1(1+1) is positive then so is (1+1)((1+1)+1) (or (2(2+1)). But from the base case we know 1(1+1) is positive, therefore so is (2(2+1), (3(3+1) and so on.
Am I right?