Cubes Sum Product Squares plus Induction Goodness

[Kirk Bevins]

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."

I am in the "I don't understand this but I would like to" camp actually. Your example is exactly why I don't like induction. You have shown that your dog is black by assuming that all dogs are black, which is nonsense.

That's exactly what induction does: I want to show that k(k+1) is positive so they assume that it's always positive from the offset. Similarly you want to show that your dog is black so they assume that all dogs are always black from the offset.

[Kirk Bevins]

"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.

I think you'll find it doesn't hold for x=-1 actually. You can't assume that because it holds for x=1 then it holds for them all!? What if it doesn't hold for x= pi over 2?

[Paul Howe]

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.

Nicely put, thank you.

Incidentally, here is a nice problem. Is it possible to tile a 2^n*2^n chessboard with one square missing, using only L-shaped pieces (i.e. they cover 3 squares)? You're not allowed any overlap, and the pieces must only cover squares on the chessboard (i.e. they can't go over the edge or the missing square).

[Kirk Bevins]

Incidentally, here is a nice problem. Is it possible to tile a 2^n*2^n chessboard with one square missing, using only L-shaped pieces (i.e. they cover 3 squares)? You're not allowed any overlap, and the pieces must only cover squares on the chessboard (i.e. they can't go over the edge or the missing square).

No. 2^n*2^n can be written as 2^2n and so whatever n is the answer will always be a product of a lot of 2s. If these L-shaped pieces only cover 3 squares at a time, you need the board to have a multiple of 6 number of squares for the L-shaped pieces to cover it exactly. Clearly lots of 2s multiplied together will never be a multiple of 6 since the prime factorisation of 6 is 2x3.

Am I right?

Edit: Shit, I didn't see the "one square missing" clause. Sorry Kai.

[Nicky]

Kirk:
From the Wiki article:

"Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one."

Since natural numbers are positive whole numbers, this does work. If it's true of 1, and it's true of n+1, (where n is a natural number) then it IS true of all natural numbers.

I think the problem is that it is a limited proof. Only true of natural whole numbers, not the whole range of numbers.

Paul:
Actually, now my brain is hurting. I've reread your posts and see where you were heading. There is still a problem with the implication/assumption semantics, but it was my mistake, not yours. Sorry. I went off at a bit of a tangent.

But what Kirk and I are doing is in effect saying - Yes, we'll all die is the sun goes supernova, but, frankly, so what? It hasn't. We aren't asking you to prove that your assumption is true, just pointing out that it doesn't prove anything about a case where the sun isn't supernova.

[Kirk Bevins]

I'll have another go.

2^2n - 1 = 3k where k is some positive integer. (In words, the total number of squares - 1 square = k lots of these shapes which cover 3 squares each).

So 2^2n = 3k + 1

Clearly this holds true for something like n=2 and k=5. Drawing a simple diagram then of a 16 square chessboard and trying to fit 5 of these L-shapes on is impossible. This leads me to the conjecture that you need an even number of L-shapes for it to work (i.e. for 2 L-shapes to fit together). This means they will come in blocks of 6 so the new problem now reads:

2^2n = 6m + 1, where m is the number of new blocks made up of 6 squares.

Clearly, any multiple of 6 is even, so 6m+1 is always odd but 2^2n is always even so it's impossible.

The only problem with this was my conjecture that these L-shaped pieces need to join together to form 6s which I haven't proved but I'm sure you could use induction. Am I close?

[Kirk Bevins]

But what Kirk and I are doing is in effect saying - Yes, we'll all die is the sun goes supernova, but, frankly, so what? It hasn't. We aren't asking you to prove that your assumption is true, just pointing out that it doesn't prove anything about a case where the sun isn't supernova.

I'm not sure that's what I was saying. I never like to assume unless I can prove it but you are assuming things in induction without proving they're correct which I tend to steer well clear of and I'm not sure why other mathematicians don't do the same?

[Gary Male]

Incidentally, here is a nice problem. Is it possible to tile a 2^n*2^n chessboard with one square missing, using only L-shaped pieces (i.e. they cover 3 squares)? You're not allowed any overlap, and the pieces must only cover squares on the chessboard (i.e. they can't go over the edge or the missing square).

Oh, that's beautiful and perfect. I have nothing more to add than "yes, it is".

[Paul Howe]

This bit...

Drawing a simple diagram then of a 16 square chessboard and trying to fit 5 of these L-shapes on is impossible.

isn't right.

[Kirk Bevins]

Ah yes!!!

I've now drawn a 4x4 chessboard and can fit 5 inside, so it is possible. How do you prove this mathematically or do you just find an example like I did?

[Charlie Reams]

You have shown that your dog is black by assuming that all dogs are black, which is nonsense.

No, I didn't. I proved that if all dogs are black then my dog is black. This is absolutely and utterly not the same as proving that my dog is black (she isn't.)

I'm not sure that's what I was saying. I never like to assume unless I can prove it but you are assuming things in induction without proving they're correct which I tend to steer well clear of and I'm not sure why other mathematicians don't do the same?

I'm going to resign at this point. After completing a maths degree and a year of teaching training you still seem to be totally confused about the absolute basics of induction as taught in A level classrooms, so I don't think I can say anything that will be useful to you. Someone with more patience may disagree. My sympathies to your students!

[David Williams]

Assume you can do it for a square of side 2^n, with one corner square left blank. Fit three of these squares together with the blank squares adjacent and fill them with another L shape. Insert the fourth square such that its blank square faces outwards. Then, by . . .

[Kirk Bevins]

I'm going to resign at this point. After completing a maths degree and a year of teaching training you still seem to be totally confused about the absolute basics of induction as taught in A level classrooms, so I don't think I can say anything that will be useful to you. Someone with more patience may disagree. My sympathies to your students!

Actually your sympathies should go to my teachers as when I didn't understand something, it's because it was very complicated to be explained and teachers had nightmares trying to explain certain stuff to me. My physics teacher gave up in the end and refused to help me.

[Paul Howe]

How do you prove this mathematically?

Telling you that would pretty much give away the whole puzzle! You're not going to like it, but the thread topic is a big hint about how you should proceed

I'm off to get my hair chopped off now, I'll come back to this thread when I've recovered my strength.

This is absolutely and utterly not the same as proving that my dog is black (she isn't.)

Racist!

[Phil Reynolds]

I don't like the "suppose" bit.

So you don't like "suppose" and "assume". Do you therefore also dislike "if"? As in, "A may or may not be true, but if it is, then B is also true"? Because that's all that's happening here. "Suppose" and "assume" in this context are just different words for "if". And if you don't like reasoning using "if", then life must be very difficult.

Have you any experience of writing software? Imagine a code fragment like this:

Code: Select all

if (i > 0)
{
    // i is positive
    print "i + 1 is positive";
}

This piece of code could be described in English as follows: "Suppose i is positive; if it is, then print the statement 'i + 1 is positive'". The fact that we've "supposed" i is positive in order to determine something about (i+1) doesn't mean that we're saying i necessarily is positive; simply that, in the cases where it is, we can say something about (i+1) - to use Paul's terminology, "i is positive" has an implication for (i+1). If you really dislike the word suppose, just reword the above description as "if i is positive, then (i+1) is positive" - which means exactly the same thing.

[Phil Reynolds]

Actually your sympathies should go to my teachers as when I didn't understand something, it's because it was very complicated to be explained

...or very simple to explain, as in the case of mathematical induction.

[Kirk Bevins]

Actually your sympathies should go to my teachers as when I didn't understand something, it's because it was very complicated to be explained

...or very simple to explain, as in the case of mathematical induction.

Well it obviously isn't very simple to explain well, Phil, else I'd have understood it 5 years ago.

My main gripe is not in the terminology of if, suppose or assume (even though I'm extremely cautious about that). I like the logic of "if I prove n to be true and I also prove n+1 to be true, then show a base case like n=1 then we're sorted". However, that's not what's going on here. You're assuming something is true to start with, without proving it.

For example: For n >2, I want to show all odd numbers are prime.

Assume that all odd n are prime numbers. Then n+1 must be even and not prime. We know for n>2 there are no consecutive prime numbers so n+1 is definitely not prime. n+2 is therefore prime as our assumption said all odd n are prime.

We must show a base case. 3 is prime, 4 is not, 5 is prime. Thus all n+2 must be prime.

[David Williams]

Maybe we should all have one stab at this. A bit like Murder on the Orient Express.

Mathematical induction is not a method that starts with any old assumption you like - all cats are black, all odd numbers are prime. It starts with an equation and shows that assuming that is true for n, it is also true for n+1. If you don't have an assumption that fits that framework, you can't use induction.

If you have some moral objection to making assumptions that's fine. Show that the equation works for n=1. Use the method to show that it therefore works for n=2. Use the method again to show it works for n=3. Persuade yourself some time this side of domesday that the method can take you to any positive integer n.

[Paul Howe]

Assume you can do it for a square of side 2^n, with one corner square left blank. Fit three of these squares together with the blank squares adjacent and fill them with another L shape. Insert the fourth square such that its blank square faces outwards. Then, by . . .

I couldn't puzzle out exactly what you meant from the description, but I think you're more or less there. Here's what I would say.

1)Assume that a 2^(n-1)*2^(n-1) board with a square missing can be L-tiled.
2)The 2^n*2^n board can be divided into 4 2^(n-1)*2^(n-1) subboards, and the missing square must be in one of these subboards. By the induction hypothesis, that subboard can be L-tiled.
3)Place an L to so that it covers one square in each subboard that doesn't have a missing square. You're then left with the problem of tiling 3 2^(n-1)*2^(n-1) subboards as if the corner square was missing, which you can do by the induction hypothesis. So now the 2^n*2^n board is L-tiled.
4)The basis is simple, a 2*2 board with a square missing is just an L, so can be trivially L-tiled.

And that's that. We've also inadvertedly done some elementary number theory, proving that 3 divides 2^(2n) - 1.

[David Williams]

If you can't puzzle out what I mean, Paul, I'll assume it's not clear! So here's a slightly longer-winded version.

Assume you can do it for a square board of side 2^n, with one corner square left blank.

Now make a square board of side 2^(n+1) by fitting four of these smaller boards together. First fit three of these boards together in an L shape with the blank corner squares adjacent to each other. Fill these three blank squares with an L-tile. Insert the fourth board such that its blank corner square faces outwards.

Then, as you can obviously do it for a 2x2 square, by induction, . . .

[Phil Reynolds]

For example: For n >2, I want to show all odd numbers are prime.

Assume that all odd n are prime numbers.

No. That's just assuming that the thing you want to prove is true, which would be circular reasoning and get you nowhere. What we assume in an inductive proof is not that it's true for all n, but that there is some n for which it's true. If we can prove the implication that it must then also be true for the next n in our series, all we then have to do is show that our initial hypothesis was correct - i.e. that there is indeed some n for which the statement is true.

Your example is not an inductive proof because you haven't begun with the assumption that there is some odd number n that is prime (which is demonstrably true), and then proved that if that is so then n+2 must also be prime. You have begun with the assumption that all odd numbers are prime, which is demonstrably false.

[Nicky]

I think I've finally got my head round this. (Thanks everyone - especially Phil). But surely if you can prove that it holds true for n, there is no need for the assumption that it is true for some n; couldn't you prove it before going on to prove it's true for n+1? Or am I still missing something? (seems likely)

[Kirk Bevins]

Your example is not an inductive proof because you haven't begun with the assumption that there is some odd number n that is prime (which is demonstrably true), and then proved that if that is so then n+2 must also be prime. You have begun with the assumption that all odd numbers are prime, which is demonstrably false.

This bit makes no sense at all to me. Also if you check previous posts regarding the n(n+1) is always positive, Michael Wallace (Sun Feb 15th 6:05pm) starts trying to prove that n(n+1) is always positive by assuming it! This is exactly what I've just done, Phil, and you shot me down. Why did nobody shoot Michael down?

[Nicky]

I think the assumption is that n is a natural number, Kirk. I think that induction only works for natural numbers. Which is how come you can prove n(n+1) i positive. Because n is positive. Not because n(n+1) is positive. I think.

[Phil Reynolds]

Also if you check previous posts regarding the n(n+1) is always positive, Michael Wallace (Sun Feb 15th 6:05pm) starts trying to prove that n(n+1) is always positive by assuming it!

No he didn't. He started by assuming that there is some value of n, which he called k, such that k(k+1) is positive.

[Kirk Bevins]

Also if you check previous posts regarding the n(n+1) is always positive, Michael Wallace (Sun Feb 15th 6:05pm) starts trying to prove that n(n+1) is always positive by assuming it!

No he didn't. He started by assuming that there is some value of n, which he called k, such that k(k+1) is positive.

Isn't this the same thing, but calling it a different letter? I remember being in my further maths class arguing with the teacher that this seemed like a pointless step.

[Phil Reynolds]

Also if you check previous posts regarding the n(n+1) is always positive, Michael Wallace (Sun Feb 15th 6:05pm) starts trying to prove that n(n+1) is always positive by assuming it!

No he didn't. He started by assuming that there is some value of n, which he called k, such that k(k+1) is positive.

Isn't this the same thing, but calling it a different letter? I remember being in my further maths class arguing with the teacher that this seemed like a pointless step.

No, it's not the same thing. Regardless of whether or not you like the idea of assuming something, can you not see that assuming a statement is true for one value of n (which is what Michael did) is different from assuming it's true for all values of n (as you did in your odd primes example)?

[Ian Volante]

No he didn't. He started by assuming that there is some value of n, which he called k, such that k(k+1) is positive.

Isn't this the same thing, but calling it a different letter? I remember being in my further maths class arguing with the teacher that this seemed like a pointless step.

No, it's not the same thing. Regardless of whether or not you like the idea of assuming something, can you not see that assuming a statement is true for one value of n (which is what Michael did) is different from assuming it's true for all values of n (as you did in your odd primes example)?

Ooh, that's made some clarity for me. At long last.

[Michael Wallace]

Yeah, I only used k to try and highlight the fact you're assuming it is true for a particular value of n. I can't really add more to this than what Phil's said.

[Kai Laddiman]

Somebody use induction to prove that induction works.

[Ian Volante]

Somebody use induction to prove that induction works.

If we assume that induction works, then induction+1 obviously works. Erm.

[Charlie Reams]

Somebody use induction to prove that induction works.

I think someone else had that idea already. Which is often a good sign.

[Gavin Chipper]

Somebody use induction to prove that induction works.

I think someone else had that idea already. Which is often a good sign.

Yes. David Hume. I think he's wrong though about the problem of induction. I think you can use this sort of induction in a limited way.