Proof of Inequalities by Mathematical Induction

Still reading though my book in Analysis, I've come across a section on proving inequalities. I'm glad to say that all of this made sense... until I reached a sub-section on proving an inequality by mathematical induction.

As  I've written previously, I find that proofs are notoriously unintuitive. In the past however, I have been particularly puzzled by the logical steps involved in proving an inequality by mathematical induction.

To explain my difficulties, let's have a look at the example provided in the book:

 

Prove that 2^n \geq n^2, for n \geq 4.

If we're proving this by mathematical induction, we generally follow these steps:

  1. Let P(n) be the statement 2^n \geq n^2.
  2. Show that P(4) is true.
  3. Assume that P(k) is also true for k \geq 4.
  4. Show that P(k) \Rightarrow P(k+1). Or rather, show that if P(k) is true, then P(k+1) is also true.

Step 4 is the key step here in the proof as it shows that if any number is true, and the next number is also true, then you can apply this rule forever, and your original statement must be true for all numbers!

Anyway, lets jump to step 2. Show that P(4) is true. Well if n=4, then 2^4 = 16 and 4^2 = 16. So P(4) is true! Easy.

Let's look at step 3. Let's ASSUME that P(k) is true for some k \geq 4.

Now, this is the part that caught me by surprise... At this step, the text in the book reads as follows:

"So, we are assuming that 2^k \geq k^2 . Multiplying this inequality by 2 we get:

2^{k+1} \geq 2k^2,

so it is therefore sufficient to prove that 2k^2 \geq (k+1)^2."

Wait, what? How is it that all of a sudden, all we need to prove is that 2k^2 \geq (k+1)^2? This isn't explained explicitly in the text so I had to close the book and do a bit more thinking.

First thing I had to realise here is that the "Step 4" I've listed above requires a bit more detail... What you're actually trying to do is show that you can progress naturally from P(k) to P(k+1). ie: We should be able to show that we can progress naturally from:
2^k \geq k^2
to:
2^{k+1} \geq (k+1)^2.

Now, if we multiply 2^k \geq k^2 by 2, as mentioned in the text, we do arrive at:
2^{k+1} \geq 2k^2

This is good, as we've managed to get the 2^{k+1} we were looking for on the left-hand side of the inequality. But the right-hand side looks nothing like the right-hand side of P(k+1) ie: (k+1)^2.

Here's the key though... It doesn't matter they they're not the same. We only need to see how 2k^2 and (k+1)^2 relate to each other. Look back at Step 3. Part of this assumption is that k \geq 4. Just as a test, let's try k=4:

2k^2 = 2 \times 4^2 = 32
and
(k+1)^2 = (4+1)^2 = 25

Well this is interesting. It's looking as if 2k^2 \geq (k+1)^2. This is exactly what was written in the text!

But to really ram it home, what we really have now is the following:

2^{k+1} \geq 2k^2 \geq (k+1)^2

So.... this show us that IF we can prove that last bit (2k^2 \geq (k+1)^2 ) is true for all k \geq 4, and not just k=4 we have managed to prove that we can get from P(k) to P(k+1)!!! This is exactly why the text in the book said "so it is therefore sufficient to prove that 2k^2 \geq (k+1)^2."

I'm sure in future I'll jump on this immediately and say "oh yes, of course that's all we need to do now", but working through the derivation of why it was sufficient was extremely useful. Long-winded... but useful.

Ah, the learning process...

Year Four Begins!

My new learning materials have finally arrived!

mu123
This is the amount of reading and exercises that I would normally have to work through over a nine-month period. Entirely doable.

However, as I've mentioned in previous posts, this module is merely to make up the credits for my first stage. Bad news is: it's all quite basic. As a result, I'll also be working through a nice fat book on analysis, to ease me in to my second stage that starts next year. As such, my nine-month work load actually looks a little more like this:

mu123plus
So we'll see how far I get with all that!

Flicking through the first couple of pages of these new materials, I realise that they cover some very basic areas of mathematics indeed. Perhaps even a little more basic than I was expecting. I think I'll have to keep reminding myself that this was my plan from the beginning, and just concentrate on submitting my assignments on time. This work will definitely be taking a back seat...

More importantly, over the past couple of weeks I've also been working through the book on analysis, and although I'm only a few pages in, it's proving to be really valuable; for one, I'm becoming a lot more comfortable with proofs and solution sets of inequalities.

0.\bar{9} = 1.0

Lara Alcock wrote in her book "How to Study for a Mathematics Degree" a warning to all mathematics students to be prepared to adjust their intuition.

Very quickly after starting with "A First Course in Mathematical Analysis" by David Brannan (see my earlier post), I have come across something that very much breaks my intuition. It turns out that 0.\bar{9}=1.0.

 

Let\: x = 0.\bar{9}

10x=9.\bar{9}

10x = 9 + x

10x-x = 9

9x = 9

x=1=0.\bar{9}

Simple, and surprising. Although also somewhat disturbing.

The equals sign tends to show that the object on one side is identical to the object on the other. In this case, they look like two completely different objects! We all know what "1" is, and 0.\bar{9} looks distinctly different.

Of course, based on Lara Alcock's advice, my first thought was "how on earth do I adjust my intuition to make this feel completely logical?!"

After some thinking, the following helped me a little bit: Before, I considered 0.\bar{9} to be a number that was infinitely close to 1, due to the infinity of "9"s after the decimal point. I now, however, consider 0.\bar{9} to be an infinitely accurate representation of 1.

For me, if I consider an approximation to be "infinitely accurate", then that approximation is the object it's trying to approximate. ie: An infinitely accurate approximation of 1 is, essentially, 1.

My opinion of this may change, but this is what's helping me make sense of this for the moment....

Fermat's Last Theorem

One of the first "Popular Maths" books I decided to pick up was Fermat's Last Theorem by Simon Singh. In the book, he expertly tells the story of Andrew Wiles and how he (practically) single-handedly solved an age-old mathematics problem. I won't go into any more detail than that because you can read a lot about the story on the web (but really don't, just buy the book).

fermatsLastTheorem

Part of what I really love about this book is that it goes into a lot of background detail, a lot of history. It builds up your understanding of why mathematics is the way it is today, and exactly why Fermat's Last Theorem was such a prestigious problem to solve.

One section that really sticks in my mind features a certain man called Bertrand Russell. Now, the more I read about modern mathematics the more his name crops up. Right at the beginning of the 20th Century, Bertrand Russell's research in logic appeared to show that mathematics was flawed. Again, I won't write down the details, I'd only end up copying Simon Singh's own words (buy the book!!!).

Although one passage did stand out in particular. Simon Singh mentioned that mathematicians obviously questioned Russell's work, and then goes on to quote Russell's response:

'But,' you might say, 'none of this shakes my belief that 2 and 2 are 4.' You are quite right, except in marginal cases - and it is only in marginal cases that you are doubtful whether a certain animal is a dog or a certain length is less than a metre. Two must be two of something, and the proposition '2 and 2 are 4' is useless unless it can be applied. Two dogs and two dogs are certainly four dogs, but cases arise in which you are doubtful whether two of them are dogs. 'Well at any rate there are four animals,' you might say. But there are microorganisms concerning which it is doubtful whether they are animals or plants. 'Well, then living organisms,' you say. But there are things of which it is doubtful whether they are living or not. You will be driven into say: 'Two entities and two entities are four entities.' When you have told me what you mean by 'entity', we will resume the argument.

A brilliant read (buy the book).

An Introduction To LaTeX

Assignment writing seems to be a very large part of studying a part-time degree in Mathematics. For my first module I hand-wrote every assignment, but with my handwriting being less than perfect I wasn't entirely happy with the neatness of the end result.

I tried numerous other ways of writing my assignments but the formatting of equations always proved to be a headache. After exploring a couple of avenues (Open Office with equation editor, and Google Docs), I decided to settle on LaTeX.

LaTeX is a formatting (or rather, typesetting) language, much like HTML in a way. For example, the following:

f(x) = x^2

is written in LaTeX as follows:

 f(x) = x^2

Which is nice. Of course this is a simple example, and the learning curve involved in producing your first 18-page assignment with it can be rather steep.

What I'd like to do every now and again is post a clever little bit of LaTeX I discover that gets me out of a hole. With any luck, after a handful of posts, LaTeX will become a lot less of a mystery.

My operating system of choice at the moment is Linux Mint. I like it because it's the only version of Linux I've ever installed that just worked straight after installation. No sound problems. No problems with network access. Everything worked.

As such, I started out by trying to work out how to get LaTeX working in Linux Mint. It turns out that to install it, you can run this in a shell:

sudo apt-get install texlive-full

This installation command should work on any Debian-based release of Linux (Ubuntu, Mint, etc...). It will install all the necessary things you need to start writing in LaTeX, including the essential command:

pdflatex

which will do the hard work of compiling your hand-typed LaTeX tex files to beautiful pdfs.

I won't be writing much about Windows, as I don't use it a great deal these days, but if you want an equivalent you can search the net for something called MiKTeX. Any actual LaTeX formatting language I write will of course work on both Linux and Windows.

More LaTeX to come!

How To Study For A Mathematics Degree

After my third module, completed in June 2005, I realised that although I enjoyed the module immensely, I still wasn't entirely happy with my ideas behind how to present proofs. Apparently this is a common problem. The shift from normal arithmetic to proofs is a jump that a lot of students find difficult.

I was so bothered by it I decided to post a query on the Open University forums about further reading. Part of my post read:

"...[I] consistently struggle with all kinds of proofs. I either start off completely incorrectly, or have no idea where to even begin."

The response was amazing, everyone (including more advanced students) agreed with me on the difficulty proofs and the shift of mindset required, and I now have a sizeable reading list to work through!

One of the books suggested in the forum was How To Study For A Mathematics Degree by Lara Alcock. I've tagged this post as being about a text book, but only because it's certainly more of a text book than a pop(ular) book. Although pitched at students that have just finished their A-levels and are about to start at university for the first time, I thought I may benefit from picking it up.

howToStudyForAMathematicsDegree

I came away with some good notes as to how to adjust my learning slightly, and she talked a lot about the basics of proofs and how to acclimatise yourself to them. One of the parts that I feel was key was the realisation that I can try to construct premises and conclusions in terms of definitions. "Starting with the definitions" seems so obvious in retrospect, but when shown something so unfamiliar it can be difficult to align your brain so as to give yourself a solid starting point. Outlining all the definitions you might need gives you that solid starting point. I'll be keeping all this in mind as I start through my first text book...

Another section I benefited from was a section on how to reading mathematics. Or rather, how to benefit whilst reading mathematics. After spending three years of reading mathematics and feeling I've so far done a pretty good job, but Lara introduced some thoughtful comments on note-taking and comprehension. Again... I'm looking forward to applying this when sifting through my next text book.

As good as the book was, I must say I didn't benefit much from the second part on "Study Skills", but this section was only about 80 pages long. The section covers what "university life" is like, and how best to be a student in such an environment. If you've already been to university it'll be of limited use, but if you're straight out of your A-levels it could make for quite an insightful read.

All in all I feel I took away from it what I wanted to take away; that is a base understand of how to approach proofs in a more structured way. At the very least, I now have a starting point!

The Maths Club

After my first year, I had a look at the clubs and societies you could join as a member of the OU. I thought it would help me feel a little less like I was learning so remotely. Sure enough, there was a mathematics club, M500.

A nice little bonus that you get for being a member is a discount for the bi-annual revision sessions that are held by the mathematics faculty at the OU. So when I started my last module, I signed up for a revision weekend that was arranged to be held about a month before my exam.

It was great meeting other students. With all that remote learning, it was great to be reminded that you weren't alone. We even had nightly trips to the pub! Just like a physical university!!!

Towards the end of the weekend, one of my fellow students, studying the same module as me, mentioned a book that he'd recently ordered.  It was written by David Brannan, a man apparently partially responsible for the syllabus of our first double-credit module in our second stage, and wrote the book to reflect the content of that module. My classmate thought he buy it to give him a bit of an edge when he finally started the monster-module. In our class he gave everyone the details. The book is called A First Course in Mathematical Analysis, and at over 450 pages, it looks like one serious introduction!

aFirstCourseInMathematicalAnalysis

Finding out about this book couldn't have been any more perfect. It means I can start my easy introductory module this year, and read through my new book on analysis so I'm ahead of the game for when my double-credit module starts in 2016! Perfecto.

Choices, choices.

It's only a few weeks now until my next module starts! The beginning of my fourth year looms...

This module choice proved to be an interesting one. My degree consists of three stages (think of them as proper university academic years), and this module will be the last of my first stage.

The last module choice is actually very broad (some of the modules are foreign languages!), but of all the modules, there is only one that has 100% mathematics content called "MU123". The only other one I would want to take has about 30% mathematics content.

The problem with MU123 is that is an introductory mathematics module. -one that I'm bound to find far too easy. Worried by this, and wondering whether I could just skip straight to the next stage I called the OU support center. They agreed that I would indeed find the module easy, but did suggest something that other students have done in the past. Previous students have taken MU123, AND the first module for the Stage 2 together and done them in the same year. The problem for me there is that the first module of Stage 2 is actually a double credit module, meaning twice the usual workload. So instead of doing one modules worth of work in a year, I'd be attempting to do three!

Faced with the absurd workload, I decided to just sign up for MU123 on it's own, have a nice easy year and get the credits I require to move on to the second stage.

Having said that, my fourth year will not be all plain sailing... more to come in a future post!

Year Three

My third module, completed last June, took me by surprise. As I'd started my statistics In February 2014, and completing in September 2014, I was hoping for a nice break before starting this third module.

The module I needed to take was MS221, rather innocently called "Exploring Mathematics". However, it transpired that the class that would be starting in September 2014 was to be the last ever of MS221. Normally this wouldn't be a problem, but MS221 followed on directly from material presented in my first module, and I was told I had to take this course. If I waited to take the replacement course I would face a ton of catch-up material .

So in summary, due to the slight course re-structure, I ended up not stopping to have a break between my second module and my third. This meant I was studying non-stop from February 2014 to July 2015. Exhausting.

I did manage to take a long holiday at the beginning of 2015, but tried to make sure I was several weeks ahead of my study before doing so.

Although "Exploring Mathematics" sounds rather unassuming, it covered some rather in-depth topics. On the one hand I was presented with proof by mathematical induction (which only proved itself to be baffling) but on the other I was also presented with group theory which describes a really nice formal form of symmetries. Seriously cannot wait to learn more about group theory...

Once July arrived, and I had taken my final exam I was once again a free man. Finally free to enjoy a Summer.

So that brings us up to date! I'm now enjoying my first proper break away from mathematics in 17 months, and the materials for my next module are due to arrive in under a month!

Year Two

After a long break from my first module, I decided to start my next module in February 2014, half-way though the academic year.

My second module was to be Statistics. I was looking forward to this, and wasn't disappointed. The module covered a lot about survey results, and how to conduct surveys effectively and make sense of the data. It also had a biology experiment thrown in there for good measure, the results of which were meant to be used in an assignment.

One of the things that really bothered me though, was their description of statistical variance. To my mind, one measure of variance would be the sum of the difference between the population mean and the sample mean, all divided by the sample count.

In fact, that's not the case. It's not divided by the sample count, it's divided by the sample count minus one. This seemed totally counter-intuitive, and apparently the full explanation was outside of the course material!!! Frustrated I scoured the web looking for an explanation... Eventually I came across a decent youtube vid. Thanks youtube!

To summarise, this video proves that sample variation s^2 is an unbiased estimator of the population variation \sigma^2 as shown below:

 \begin{align*} E(s^2) =& E \left( \frac{ \sum_{i=1}^n( x_i - \bar{x} )^2 }{n-1}\right) = \sigma^2 \end{align*}

See that pesky "n-1" divisor? Check out the full explanation here.

So after my study starting in February and ending in September, I felt I'd had a decent introduction to statistics.

Although, something that does surprise me is that looking ahead at my possible future module choices... statistics doesn't really crop up again for the rest of my maths degree. With the growing importance of statistics in modern society (let alone mathematics itself!) I would have expected a lot more of those modules on offer. Having said that, there is a separate BSc (hons) Mathematics and Statistics that the OU offers, but this appears to almost be purely statistics and doesn't give much variety. -certainly wouldn't be good for me.

In fact, there are  only two real interesting modules on this Maths and Stats degree course, one of which is the final year module "Mathematical Statistics" (M347) that introduces Markov Chain Monte Carlo, which is an area of interest. I suppose after my ten-year degree, if I'm still desperate for more, I can sign up for it as a stand-alone module. 🙂