Tuesday, June 26, 2007

Yet another slimy Proof (by induction?)

If you've just fallen of your chair to find me awake at this time then I do apologise. (What you don't think I haven't slept yet do you?!) Due to unfortunate (I claim!) circumstances I am awake at this weird time! I'm not too happy, since five minutes ago I learnt that I could have slept another hour. Not exactly five minutes -that's just me being vague as you do. Unsurprisingly lack of sleep initially means that I'm fully wake, and as this post will demonstrate slightly .... ? (Can't think of that word). BTW I haven't forgotten about my slimy story, which it seems is only fascinating to myself. *sniff* More on that at the end.

So to business. I didn't wake up and think 'bham I've got to post about this,' so we can all relax. (Un)fortunately my posts about maths are going to be quite random maybe. I'll try to avoid this, however upon reading this post at Modulo Errors I thought it necessary to discuss Proofs (note the capital P!) amongst other essentials in Maths. Analysis really refines the art of proofs and I believe it's important that I lay out the path nicely rather than trying to jump over the wall.

Initially it is easy to be overwhelmed by Proofs. We don't realise what is happening, but know so much to realise that we don't like the module Sets, Numbers and Functions (SNF). We prefer calculus. Proofs do crop up there, but we're more familiar with them (eg trig proofs). It's like being injected with a drug and your body has a bad reaction to it. That was what happened to me. We all react in different way (unless of course you're twins and have the same DNA... Biologists don't shoot me if that's wrong!). Thus our immune systems help us to overcome this 'illness' at different rates and different ways. Some people might need medication (eg me!) whereas others are able to battle it out on their own. Basically, for a majority of students starting on a maths degree either you 'don't like' proofs or you have no preference towards them. However I think a majority of students don't really understand how vital proofs actually are.

There are many reasons as to why students could possibly not like proofs. I have probably said this a million and one times, and so will say it again! I did further maths and if memory serves me well in FP1 we learnt about induction. I'm not sure whether or not to think that my teacher did a brilliant thing, since effectively I'd learnt it 'algorithmically'. I was clueless really as to what I used to be doing. All I knew was that if I didn't mention 'since this is true n+1 times, it's true for all n' or something along them lines I'd lose a mark! [Having now come across quantifiers, I do recall Mrs. B telling us about this symbol,\<span class=forall"> (for all), once upon a time.] The fact remains that when I was taught induction at university I was actually worse off than students who probably hadn't done it before. (maybe). Whilst we were taught it I used to get muddled up a lot since all I wanted to do was chop something from here and move it down there, and rearrange to get the right hand side. I never understood it and always used to assume the result and then say it's true!! Like I said credit has to be given to Mrs. B, since I don't think I ever really understood understood FP1. I say this because I find it extremely difficult to remember anything else that we did.

As it has been mentioned in Blogistan it is fundamental that you understand and get your head around proof by induction. Another confession I have is that the only reason I didn't answer the question on Induction in our January SNF exam, was because even then I had sucked majorly at proof by induction. I had tried to revise it but the cogs just wouldn't click. The Tweenies were in shock at this, since they felt that was one of the easiest questions on the paper. Even now I'd probably disagree since I do tend to find induction a challenge.

Before I give an example of induction, I'd like to continue discussion as to why students don't like proofs. In college C3 had an element of proofs to it but we weren't taught this chapter since the teacher said it should only be a few marks, and it doesn't matter if we drop them marks. At the end of the day a question did come on the exam paper- it wasn't too taxing, but that being said I still missed one part of it out. (Something about Pythagorean triplets). I do also recall the C3 text book having a chapter about proofs and the word 'contradiction' cropped up as well.

In my case the problem with proofs probably began in college. In FP2 I can't recall ever consciously thinking that 'yes I'm proving this'. It's about notation(?). The nature of proof should be made clear in college. You see I say all these things, but I'm not complaining about my experience of such things. I don't know how different things would have been if I'd understood said concepts, but my experience has got me to where I am today. I've learnt from it (hopefully) and glad of it.

So we start university with a vague idea of proofs. The first week of lectures we are introduced to most types of proofs- contradiction, example, direct etc. We don't understand these but it's our first week, things should fall into place soon. It's time to do the problem sheet. Things haven't fallen into place!! We look towards the example in lectures and try to follow the book, but still we fail miserably. 'Contradiction- it's stupid' and a few other well chosen expletives we conclude. Why- because we have no idea how we're meant to go about our business.

The weeks go on and all we're seeing is different colourful proofs in all shapes and sizes. You copy them out blindly, wishing for them to make sense. Slowly we start hating them. Not hating hating them, but we become sick of them. We don't want anymore- they don't taste nice. We have yet to understand how important they are. Then one day, after numerous complaints on the feedback forms, the new lecturer (who gave lots of proofs!) explains that why do a maths degree if you don't want to do proofs? We know somewhere in our heads that he's got a point, but still we don't like proofs. Not for long though.

Now in terms of university proofs and being able to follow them I think it is absolutely crucial that you understand the DEFINITIONS of things. Yes, that is one of the main things when it comes to formal proofs. If you don't get the bigger picture in lectures- don't worry. All you should initially worry about is getting to grips with the definitions. Be able to say them from the top of your head in your own personal style. Trust me on this- definitions are really important. After that focus on trying to understand what a theorem is actually telling you. I will write more about this in due course but it starts with the definitions in my opinion.

When does it finally fit into place, I hear you ask? (ahem!) Like I said- how we react and get over this illness is different. My initial motivation kicked in when Dr C started lecturing us (his proofs were plain cool- I could follow one step to another most times even if I didn't get the big picture). This motivation caused me to work. Working allowed the rusty cogs in my head to start moving. Working slowly started curing me! That's what did it for me, however I needed motivation to work, whereas the next person may not. I'm not going to pretend otherwise but some proofs still go whoosh over my head. However the difference is in my change of attitude towards them. No longer do I internally suffer when I hear the word proof. Now when presented with a theorem I want the proof!

A proof is a logical argument which establishes the truth of the statement. Proofs are necessary because they allow us to make statements which are true! We could claim a certain thing (conjecture) however until we have a proof we are not to know whether this claim is actually true. We cannot assume it to be true since, even if the counter example isn't eg 900000, it could be a bigger number-we don't know. The point being that one may exist. 'The concept of proof is absolutely fundamental to mathematics. In fact one may fairly claim that without proof (pure) mathematics does not exist.'1 Each step in a proof must be true, either deduced from previous statements or the assumptions made. I will be writing more on different types of proofs and what exactly a proof consists on another time, however they really are the building blocks of maths and it is important that we understand that. Only when we properly understand the concepts of proofs and the different types of proofs will we be able to construct them ourselves. (I live in hope- that's one thing I'm rubbish at!)

So back to induction now and my example. Before I go further, I would once again like to say a big thanks to Dr Coleman. Yes- you've got it, he helped me understand proof by induction after one popped up in sequences and series! (They're everywhere!) Honestly, I was slightly embarrassed, since the Tweenies were all trying to explain to me what's going on but it wasn't making sense. Why, because I didn't understand what I should be doing. I had been assuming what we're supposed to proof and then messing around with it. It's not necessary to understand the 'tricks' etc of proofs but the concept should be understood. The concept of induction should be understood since it also pops up in linear algebra and everywhere else! Thanks to Dr C. I feel I know how to tackle proofs by induction and how to go about doing them- trust me it was a a struggle.

From my lecture notes, the induction principle is:
Suppose that P(n) is a statement involving a general positive integer n. Then P(n) is true for all positive integers 1, 2, 3... if,
i) P(1) is true (i.e. the base case)
ii) P(k) \<span class= for all positive integers k.

That is the general case, however we can use the same idea and start with any other integer as the base case. 'Suppose that n_0 is an integer- positive, negative or zero. Induction can be used to prove that a statement P(n) is true for all integers n such that n\<span class=ge n_0">. The base case is now P(n_0) and the induction step is P(k) \<span class= for k\<span class=.'2

I'm delaying the example, but if I claim A \<span class=, then you'd either start with A and deduce B, or start with B and show A. You only consider one side of the argument, and then use that to show the other side. You can't start with one side and then all of a sudden jump to the other! In this case you have a choice of which side to consider first.

The example3:

Claim \<span class=

You may find it useful to identify P(n), which in this case is 2n+1 \<span class=.

So we first check the base case, and in our case that is when n=3. We are trying to show that P(3) is true.

\\2 \times 3+1 =7\\ 2^3=8\\ \text{and } 7 \<span class=

Then we proceed by assuming that the result is true when n=k, i.e. that 2k+1 \<span class= is true.

The next step is one of the most important ones (in my opinion). We want to show P(k+1) is true. That is what we want. We don't know anything about P(k+1). It might be true but we don't know that -we WANT to show it's true. That is why I mentioned the bit about trying to show that A \<span class=. We start we one side on the statement to show the other, and in our example we apply the same argument. We start with one side of P(k+1) and try to deduce that the other side is true.


\\\text{The LHS of }P(k+1)\text{ is }2(k+1)+1\\ =2k+3 = (2k+1)+2\\ \le 2^k+2^1\text{ by the induction hypothesis}\\ \le 2^k+2^k \text{ since } k \ge 3 \ge 1 \\ =2 \times 2^k=2^{k+1},\\ \text{which is the RHS of }P(k+1).

\text{So <span class=

Hence, by induction 2n+1 \<span class= is true \<span class=.

\<span class=

What to do: make it clear what P(n), the base case and P(k+1) are. I think it's good to let the reader now what you're doing and so have written things like 'by the induction hypothesis' when they were used. We were able to do that step since we have assumed that P(k) is true.

What not to do: Say 'assume P(k+1) is true'. Yes, I used to do that all the time- it's wrong. We don't know anything about the truth of P(k+1), we just showed that. The aim of the game is to show the truth of P(k+1). We cannot start by saying it's true!

I'm sure there are many other dos and don't so feel free to add to them. If I was being perfectly honest, I don't really fully get the 'trick' when we use k \<span class=. I slightly understand why we do it, but it's not properly 'clicked' yet in the sense that if I was to help someone doing this proof I wouldn't know how to explain it to them. It's used a lot in such proofs and so if you understand it that's great.

There you have it- induction in a nut shell. If I've missed anything out, or written something absurd please do let me know. I'm not going to get the chance to check through this straight away. I also can't remember what else I was supposed to write. :/ The slimy tale I'm afraid will have to continue in a post later today- I am running late, but if you haven't been following the story here's your chance to catch up!

*(meh- nothing apart from TeXnic centre understood my formula. :( ) EDIT: fixed thanks to Steve. :)
1 Allenby: Numbers and Proofs
2 Dr Eccles: An introduction to Mathematical Reasoning


steve said...

*(meh- nothing apart from TeXnic centre understood my formula.

Use this code instead which will work:
\\\text{Consider LHS }P(k+1)=2(k+1)+1\\
=2k+3 = (2k+1)+2\\
\le 2^k+2^l\text{ by the induction hypothesis}\\
\le 2^k+2^k \text{ since } k \ge 3 \ge 1 \\
=2 \times 2^k=2^{k+1}\\
=\text{RHS }P(k+1)

Another point though. P(k+1) is a statement so it cannot equal a number. Thus I would write the first line as
LHS of P(k+1) is 2(k+1)+1 = ...

I usually explain induction in terms of a robot. Suppose you wish your robot to be able to climb stairs however high. Then you only need to tell it 2 things:
1. how to get to the bottom of the stairs;
2. how to get from one step to the next.
Both are crucial, but they are enough to enable the robot to climb as many steps as you wish.

beans said...

Thanks Steve. I had tried writing in eqnarray, but that hadn't worked as well! (and thanks for the correction. :))

That's a good way of explaining it. The one that I was told at university was the 'domino' concept.

'Suppose that we think of the integers lined up like dominoes. The inductive step tells us that they are close enough for each domino to knock over the next one, the base case tells us that the first domino falls over, the conclusion is that they all fall over'

(Taken from Dr Eccle's book- An introduction to mathematical reasoning).

Never mind induction- now I have to try and work my head around strong induction! :/ (There were many proofs used in SNF lectures using strong induction- let's just say that require another look at!)

Jake said...

Another point though. P(k+1) is a statement so it cannot equal a number. Thus I would write the first line as
LHS of P(k+1) is 2(k+1)+1 = ...

One of our lecturers used the notation 'such that' i.e. ':' for propositions... I don't know if this is standard though.

e.g. Let P(n): n/2 + (2n)/4 = n

It sounds strange to read it thus... 'let P(n) such that half n plus half n is equal to n' but it is an easy notation and avoids the common fallacy of misusing implies and equals symbols.

The more I read about A-level maths and the more that I have seen the perception of mathematics from my fellow university students, the gladder I am that I didn't do A-levels and instead learnt the basic material from books. That way, by the time I got to university, I at least had a fair idea of what different areas were and what maths was all about. I was quite fortunate in some ways that the first bit of mathematics that I did after GCSE was from a university algebra book. It was very hard and confusing at first but at least I was introduced to the important concepts of what mathematics is early on, so as I struggled with that book and started to do basic calculus (which was easier to pick up) I at least had an appreciation for proof and understood that I was learning technique and methods and that one day I would have to get round to justifying that the methods and techniques were legitimate.

beans said...

I can't say that I've seen ':' used in statements like that, but if you get rid of the 'let' it makes some sense I suppose. :p I tend to always put equals symbols in the wrong places! In college you'd just stick an equal signs to mean then. (well that's what I did).

(I've seen that in set notation though {P(n)= n : n \in Z}, but that's quite different I guess).

I think you're lucky to have done it your way and understood the foundations for everything. In a way your education has been 'pure'. I do sometimes wonder what things would have been like had I still been in my previous fog of not aprreciating proofs. I suppose I've been lucky to a certain degree as well. I can't really comment too much on A level maths, since for me I always preferred further maths and didn't particularly like my normal maths lessons. (Reasons for this will be mentioned in my college post!)

I think a bridge has to be made between universities and colleges for students who accept offers to study maths at university. It'd be nice to start the year at a slight jog, as opposed to first walking backwards and then slowly making some progress. This way the students know of what is to come, and are hopefully eager to get started. Maybe the lectures which we had in the first week introducing us to proofs etc could be done to students who've accepted offers. Then they could be given a 'reading list' and told to have a good summer and get ready for the next year? (Voluntary of course- you don't have to attend!)

I'm not sure which side of the fence to sit on, because I don't really know how other undergraduate students feel about this. On one hand I am grateful for the experience, but then again I do wonder how things could have been different.

Jake said...

I can't say that I've seen ':' used in statements like that, but if you get rid of the 'let' it makes some sense I suppose. :p I tend to always put equals symbols in the wrong places! In college you'd just stick an equal signs to mean then. (well that's what I did).

(I've seen that in set notation though {P(n)= n : n \in Z}, but that's quite different I guess).

No, the 'let' is the point here, I mean the notation is used to define the variable proposition.

i.e. let p(n) be the proposition stating that n = n/2 + n/2.

Assuming that in {P(n)= n : n \in Z}
P(n) is a function (rather than a proposition), then that would be the normal use of 'such that' and that set would be the set of integral points on the curve p(x) - x = 0 that intersect with the line y = x.

beans said...

Ah, I see what you mean. However if you write, 'let P(n) be the proposition such that n=n/2 +n/2' then that also makes sense.

P(n) is a function...

[Once again another 'ah' :o I was in another planet about this for a while!]

Jake said...

The notation is also commonly used with propositions when defining sets e.g. {n: P(n)}

i.e. the set of numbers 'n' such that the variable proposition P(n) is true.

So, for example, in proofs by induction, you are often trying to show that for some proposition
P(n), {n:P(n)} = N, where N is the natural numbers.

Equally, you could use the notation to define the solution set of a curve e.g.

let P(x): f(x) = 0

(P(x) is a variable proposition, f(x) is a function)

then {n: P(x)} would be the set of solutions of the equation f(x)=0.

I just realised that in my previous comment, I posted
{P(n)= n : n \in Z} when I in fact meant to say {n \in Z:P(n)= n}
where P(n) is a function. Of course, the first is meaningless.
Hopefully, the lateness of the hour suffices as excuse :)

beans said...

(Don't worry- I always either blame the time or lack of sleep!)

Why is the first meaningless?

The first would say the function P(n)=n such that n is an integer, and the second one says n is an integer such that P(n)=n. What's the difference?

I normally wouldn't write P(n) but just {n | n \in Z}. (I can't even use the time as an excuse for being dumb!:o)

Jake said...

Why is the first meaningless?

The first would say the function P(n)=n such that n is an integer, and the second one says n is an integer such that P(n)=n. What's the difference?

But 'P(n)=n' isn't a function; it is a statement saying that the value of a function at a given point is equal to that point.

The form that I was using was 'the elements such that a variable proposition is true for those elements' (where the proposition happened to be
vprop(n) states p(n)=n). If you reverse it and say 'a variable proposition is true such that an element' then it just doesn't make sense.

As a more clarifying example, consider the following sets:

let A = {1,2,...,10}

let B = {n in Z: 3n+1 in A}

let C = {3n+1 in A: n in Z}

Now B and C are effectively 'the other way round' in terms of the 'such that' but

B = {0,1,2,3}
whereas C = {1,4,7,10}

You have to think about what these things are saying in words and the order is normally important.

To put it simply; such that isn't 'commutatative'.

beans said...

I see what you mean, I was getting in a muddle over P(n)=n being a function when it isn't- it's effectively a formula. (I really did mess up in the first 6 weeks of the course! :o)

Thanks it makes sense now.:) I think I have incorrectly used this notation on a few occasins then, since I didn't really think twice about the order I wrote things!

Anonymous said...

why are u still studying when term is finished and ur meant to be on holiday

beans said...

I don't think that we should ever stop educating ourselves. I won't say that I've been studying (yet :( ), but I thought that after all this is some sort of maths blog and I might as well give that some justification!

We have three months of holidays- would you not study maths in them three months??! So do you only study during term time? :p [I'm just slowly trying to encourage myself to do the reading around the subject that I didn't last year. :)]

This is my holiday :D Well for another week or so. ;)

Jake said...

why are u still studying when term is finished and ur meant to be on holiday

University (for students) isn't work; one goes there in order to aid the learning process, this doesn't mean that one should let it entirely dictate that.

I mean I went to university to follow, in a more formal sense, something that had already been a hobby of mine (i.e. mathematics)