Heidi Newton

Rediscovering a passion for math

Just over a year ago, I decided to challenge myself and give math another go, even though I had given up on the idea of double majoring in it some years earlier. With excellent online resources and lots of hard work, I've managed to re-discover the love I had for math when I was younger. Proofs, which I used to be convinced were intended to be torture devices for students, are now addictively fun to write!

In this blog post, I share my experiences getting back into math. I hope some of the resources and ideas might act as an inspiration to at least one other person who began to resent math as they got into senior high school and university.

My experiences with math in school and university

As a primary school student, I loved math and especially problem-solving competitions. I even got some impressive placings in a few. I loved being able to analyze a challenging problem, and then come up with a creative way of solving it. I didn’t learn algebraic techniques until quite late, instead preferring trial and error methods combined with pattern recognition and what I now understand is binary search.

In high school, I thought proofs were something for teachers to do at lightning speed on the whiteboard, and that was impossible for kids to understand. I cringed when my physics or calculus teacher said: "Okay, now I'll prove that for you". It consisted of lots of frantic scribbles on the whiteboard and conclusions that seemed to be drawn out of nowhere. It seemed like if you did lots of scribbles on the board, said lots of stuff that I, and I suspect others in the class, did not understand, and then say "therefore, we use this formula!" then it was the indisputable truth.

When I got to 1st-year university, I thought proofs were something I wasn’t smart enough to write. I would stare at the theorem, claim, proposition, or supposedly trivial lemma for hours and have no idea what to do with it. Then, I’d go to class the next day, and the lecturer or tutor would come up with some “outside the box” piece of reasoning, or “magical” rearranging of the formula on the spot, and complete the proof quickly. I would then try to apply that "outside the box" piece of reasoning to the next proof, but then it didn't work, and the lecturer would have a completely different "outside the box" bit of logic for that one. I would try to memorize all of their pieces of "outside the box" reasoning for the exam, but those evil lecturers, they would give questions in the exam where none of those memorized "reasonings" would work. I didn't know what I was expected to do! Many of my classmates must have been even more clueless about 1st-year discrete math, as I got an A+ due to heavy upscaling of the final exam. I had personally thought I'd gotten a B+, so the A+ was a big surprise.

I did a couple of discrete math papers in my 2nd year; one in cryptography, and the other in discrete structures. I did okay in the discrete structures one, as the proofs were reasonably straightforward. Additionally, the lecturer was very aware of all the computer science majors in the course and so told us to write our proofs in English rather than math symbols if we weren't confident with notation. I wonder what computer science students had been handing into him on previous years to scare him into encouraging us to write proofs in English! I enjoyed that class, the proofs were generally a bit difficult to figure out, but then easy to write up as they tended to be super elegant pigeonhole principle arguments and stuff like that. Therefore, the focus was much more on problem-solving than the terrifying "proof writing".

Just over a year ago, I started to wonder how it was that I was so good at math in school and then ended up despising the subject as I got into late high school, and then university. I decided it was time to give it another go, using online courses and resources. It’s been about a year now since I rebooted my new mathematical journey, and to say the least, it's felt very successful and fun. All the hours of my spare time that have gone into it have been well worth it!

Khan Academy's school-level math

Khan Academy is a website that, among other things, has resources to teach an extensive range of fundamental math ideas. It is based on the US curriculum, but due to being such a complete collection, it probably covers almost any primary school or high school math curriculum. If you need to fill in any gaps, it has got to be the number one place to go!

Something I really like about the design of Khan Academy is that it provides pre-tests to let you identify where your misunderstandings are (as sometimes, this is difficult even to know), and then has the resources to address those misunderstandings. The coverage is extensive, so you can be reasonably confident you've mastered everything at the high school level. I wish this resource had existed when I was in high school.

I realized that my lack of confidence with math notation and algebraic rearranging was a significant roadblock to doing more complicated math and constructing proofs. In areas such as math and computer science, each concept builds on top of the last. Misunderstand an early concept, and there’s a lot you won’t understand by the end. So, my first step was to address that using Khan Academy’s impressive resources.

To ensure I didn’t miss anything, I started back at Khan Academy’s pre-algebra course. This one didn’t take too long to complete, although interestingly there was a couple of areas where I had misunderstandings to correct! I then worked through algebra 1 (easy), geometry (lots of stuff I didn’t know), algebra 2 (mostly easy, but also some new content), trigonometry (lots of challenges as I didn’t get it at all in school), and precalculus (challenging but lots and lots of fun). My favourite was probably the geometry with all its proofs. Complex numbers were also a highlight, as I didn’t like them in school, but found them super interesting and fun this time around. Overall, there was no area of math I didn’t like, not even trigonometry. The way I think about trigonometry is entirely different now to what it was before I went through these courses. I learned a lot of algebraic rearranging techniques I’d never seen before too. Above all, though, I re-discovered the love for math I had in primary school and was more than ready to go further!

I intend to go back and do the calculus stuff very soon, to see if this resource can even treat the fear of calculus I developed over year 13 and 1st-year university.

Keith Devlin’s Introduction to Mathematical Thinking

The course can be found on Coursea.. Unlike most of the good Coursea courses, this one is entirely free! Keith Devlin is a math professor who mostly focuses on ways of getting people to learn and enjoy math. In this course, his goal is to help learners think like mathematicians and to understand the difference between high school math and professional mathematicians.

The course starts by teaching fundamental ideas in logic, and especially implication. It then goes into proof techniques, and then examples of proofs pulled from number theory and real analysis. The main goal, though, is to think like a mathematician. Instead of applying a formula to problems, you instead have to think in a unique way, called mathematical thinking.

Getting to the airport gate on time: thinking like a mathematician!

One of my favourite problems he shares (not an original problem) in the course goes like this.

You are in the airport, heading to your gate, and notice your shoelace is undone. You need to tie it back up and have 2 options. You can a) stop where you are and tie it, or b) step onto the travelator and tie it. You’ll use the travelator regardless, and if you aren’t tying your shoelace on it, you’ll be walking on it (moving extra fast). You’ll take the same amount of time to tie your shoelace regardless of where you tie it. Which option will get you to your gate fastest though?

Have a think before reading any further!

The question doesn’t tell you your walking speed, travelator speed, distance to gate, length of travellator, or time to tie a shoelace, because you do not need to know these details to solve it. Because he doesn’t give the answer, the class forum is full of arguments for all 3 possibilities (where you are, on the travelator, or doesn’t make a difference). However, after a bit of thought, I realized there’s at least one way of thinking about it where the answer is indisputable.

Many people say it doesn't make a difference. Even James came to that conclusion until I put the following to him. Imagine you, and I are at the airport, and our shoelaces come undone at the same time, right when we were about to step onto the travelator. You stay where you are and tie yours, and I step on and tie mine once I am on the travelator. After a while, we both finish tying at the same time and continue walking. Regardless of whether or not I’m still on the travelator, or how long it is, there’s no way for you to catch up to me. Last time we were at Sydney airport, which has those awesome travelators, we even acted the scenario out. I’m sure other people thought we were weird, but nobody called security, so all was good!

In summary, it turns out it's better to step onto the travelator and tie it while on the travelator.

Moreover, that is the difference between high school math and mathematical thinking. We shouldn't do lots of calculations; we should instead come up with a straightforward logical argument.

If proofs are fun: then you understand logical implication!

The other thing I found helpful was how he taught logical implication. My first-year discrete math course at the University of Canterbury did induction very early in the course, and I struggled with it. I’ve since realized this was because I didn’t fully understand implication. In case any readers are not familiar (or still struggle with) implication, here’s a quick summary.

Logical implication is a statement of the form if a then b. The implication is valid if b is always true when a is true. When a is false, we don’t care what b is. It’s equivalent to saying either b is true, or a is false (both are allowed to be true!). If it is ever possible for a to be false, but b to be true, then it is not a valid implication.

Keith Devlin talks about how many students struggle with implication, and quantifiers, and therefore gives heaps of practice questions for them, insisting that they are mastered before moving any further. It made me feel a lot better realizing this is a common challenge for math students, and therefore, it didn’t suggest I couldn’t be successful at math! One cool example he gave, that I remembered every time I was getting confused was as follows.

If Keith wins the cycle race, then he practised a lot. This statement is true because there’s practically no chance he’d win without practising heaps. However, that does not mean If Keith practices a lot, then he'll win the cycle race. Of course, in life, even if we try super hard, there are no guarantees. This illustrates that if a then b does not always mean if b then a, like many students, I included in university, think it must.

Getting my head around implication has made induction, and many proofs, a lot easier to think about. I now realize it’s a waste of time even trying to do proofs if you haven’t gotten a firm grip on implication. Proofs are centred around implication, and so trying to prove something without understanding implication is like trying to win a car race without knowing where the accelerator is.

Closing thoughts on mathematical thinking

I’d recommend this course for high school students considering going further in math or a related field. The pace of the course isn't too fast as long as you put the time in and do all the assignments, and it really introduces you to what math is in further study, and what it isn’t. For those who just like applying formulas, they might realize math isn’t for them. For those who like reasoning and logic, they might realize that even if that was limited in school, there’s going to be more and more of it going forward. The course also does a good job of slowly working through some of the fundamental ideas that must be mastered before going any further (logic, in particular, implication, and quantifiers) that can act as early snags and off putters for students. Overall, you’ll be introduced to what it means to think like a mathematician, and guided through your first baby steps towards that lifelong thinking goal.

If I wasn't addicted to proofs by the time I had finished the geometry unit on Khan Academy, I was most definitely addicted to them after doing Keith Devlin's course!

MIT’s Mathematics for Computer Science

Something not everybody knows is that one of the best universities in the whole world publishes almost all of its course materials online, free, for anybody to access! Their philosophy is that everybody should have access to education. It’s very cool that even if not everybody can attend MIT, that if they want to, they can still learn the same stuff an MIT student would. So with that, here is a super awesome course on MIT’s OpenCourseWare.

At the moment, I’m working through this course. I’ve done all of the first unit, the proofs, and am currently working on the second unit, discrete structures. The content in this course is mostly beyond what I did in 2nd-year university, and so is mostly new to me. The proofs are challenging, but satisfying when you find a way of proving something you previously thought was impossible to prove, and above all, the questions are just a lot of fun!

Well-Ordering Principle: The power of the obvious

Almost from the start, the sturdy pedagogical design of the course is clear. Instead of launching almost straight into induction like so many mathematics for computer science courses do, this course starts with something called the Well Ordering Principle (WOP). It’s just induction phrased differently, but the way you think about it is entirely different. In any non-empty set of non-negative integers, there is always a smallest element. Isn't that the most groundbreaking thing you've ever heard? No?

Unless you've heard of it before, what I just stated was probably so obvious to you, that you think you’re misunderstanding. Don’t worry; you're not: it’s obvious! It’s not true for negative integers though, unless we have a lower bound. The set of all negative integers (or all integers in fact) has no smallest element because you can always find a smaller one, going infinitely more and more negative. However, for all positive numbers, the smallest element is 1, and for all non-negative numbers, the smallest element is 0. If we have a set of negative integers that are the negative integers above -10, then we do have a smallest element, as it no longer goes infinitely lower.

Sometimes in math, the most obvious things can turn out very powerful. Here’s an example from the class, of the WOP in action.

Let’s say we have as many 3-cent and 5-cent postage stamps as we need. A number is considered postal if it can be made with a combination of these stamps. It turns out that any number 8 or above is postal (using this definition).

The proof is as follows. Just like induction, we have a few "base" cases.

  • We can make 8 using 3-cent + 5-cent
  • We can make 9 using 3-cent + 3-cent + 3-cent
  • We can make 10 using 5-cent + 5-cent

Now we can prove the rest by contradiction.

For the statement to not be true (we’re proving by contradiction), there must be at least one counter-example, i.e. a number greater than 10, that is not postal. Let C be the set of all such counter-examples.

Now, because C is not empty, and all members of C are positive integers greater than 10, we know that C must have a smallest value, thanks to the Well-Ordering Principle.

Let n be the smallest value in C that is, the smallest integer that is not postal. Because n is the smallest integer that is not postal, we know that n - 3 must be postal. However, if n - 3 is postal, then we can easily construct stamps for n by just adding a 3-cent stamp to the solution for n - 3. Therefore, n couldn’t have been the smallest counter-example, which is a contradiction as n was supposed to be the smallest in C.

Because we got a contradiction, we know that the original statement is true, which concludes the proof.

This is the beauty of the WOP; we can use it for elegant proofs by contradiction by saying there must be a smallest counter-example to the statement we’re trying to prove as always true, and then forcing it into a contraction by showing that either there has to have been a smaller-than-the-smallest counter-example (which is of course nonsensical!) or that there, in fact, it is true for the smallest counter-example. It doesn’t require much formal math to understand, yet it is a compelling technique, and so gives a gentle but powerful starting point for those starting to learn to construct proofs.

Later in the course, he talks about the pedagogy behind starting with the WOP instead of induction. Apparently, it’s controversial; some think it’s not necessary. As somebody who initially struggled with induction though, I’m all for it. It helps to reduce the number of new things that have to be learnt to get started with proofs. Once students then get to induction, they have fewer things to have to grapple with for the first time. Surely that could only be a good thing, right?

Preserved invariants in state machines: my favourite math idea ever!

While the Well-Ordering Principle is pretty impressive, my favourite thing I've learnt so far was preserved invariants (often just called “invariants”) in state machines. I had never done those before, and wow are they awesome!

In case anybody reading this needs a reminder, state machines are a bunch of states something could be in, with transitions to get between them. For example, in a game of chess, the states are all the valid configurations for the board, and the transitions are the moves the players use to get between those states.

A preserved invariant is something true for every state that is reachable. One example of this in chess is that the bishops can be (the bishops are the pieces that can only move diagonally). Each player gets 2 to start with: one starting on a white square, and one starting on a black square. Because we can only move the bishops diagonally, it’s impossible to have them both on the same colour square (unless a pawn was promoted, but let’s assume for now that pawns can only be promoted to queens). If a player ever has both of their bishops (and hasn’t promoted any pawns to bishops) sitting on the same colour of square, it’s evident that at some point, somebody moved a bishop incorrectly, or accidentally knocked one to a different square. Therefore, for the bishop that starts on a white square, it will always be on a white square (and same for black square bishop). Something that must be true of all states is called a preserved invariant of the state machine (or system).

The reason I love this technique, though, is not because of chess, but because of the power of the reasoning, you can use it for. Take for example that puzzle where you have a 3-litre jug, a 5-litre jug and a tap, and have to somehow measure exactly 4 litres into the big jug. In this case, it’s straightforward to come up with a solution. When we pour one jug into the other, we only pour as much as will fit. No water should be lost when transferring water from one jug to the other.

  1. Fill the large jug. [5 in large, 0 in small].
  2. Pour the large jug into the small jug. [2 in large, 3 in small]
  3. Empty the small jug. [2 in large, 0 in small]
  4. Pour the large jug into the small jug. [0 in large, 2 in small]
  5. Fill the large jug. [5 in large, 2 in small]
  6. Pour the large jug into the small jug. [4 in large, 3 in small]

Done!

So now, what if instead, you have a 9-litre jug and a 15-litre jug. How can we measure 4 litres this time? The short answer is we can't, and that we can even improve that it's impossible. How? Using preserved invariants! Let's start with some quick terminology.

A state is the current amount of water in each jug. We can represent states as 2 integers; one is saying the amount in the first jug, and the other saying the amount in the second jug. The starting state is always ( 0,0), as both jugs start empty.

A transition is a move we can make to go from one state to another. There are 6 different transitions we can make. (x, y) means there are currently x litres in the big jug and y litres in the small jug. The bit after the shows how the amounts will change in the transition, relative to what they were before it.

  1. Fill the big jug: (x, y) → (15, y)
  2. Fill the little jug: (x, y) → (x, 9)
  3. Empty the big jug: (x, y) → (0, y)
  4. Empty the little jug: (x, y) → (x, 0)
  5. Big jug into little jug: (x, y) → ((max of 0 and x + y - 9), (min of 9 and x + y))
  6. Little jug into big jug: (x, y) → ((min of 15 and x + y), (max of 0 and x + y - 15))

The last 2 use the min and max functions to ensure water is never spilt on the ground during them.

We always start with empty jugs; (0, 0). I claim that all of the transitions will always ensure that the amount in the big jug is divisible by 3, and the amount in the small jug is divisible by 3. To prove my claim, I need to show that it is true in the initial state and that it is preserved by all of the transitions. In other words, every transition, if given (x, y) where x and y are both divisible by 3, must give a result (x1, y1) where x1 and y1 are both divisible by 3.

Because 0 is divisible by 3, the claim is true in the initial state.

For the first 4 transitions, the proof is straightforward. We are assuming that x and y are divisible by 3. We also know that 0, 9, and 15 are all divisible by 3. Therefore, everything on the right-hand side of the first 4 transitions is divisible by 3.

For the last 2, we need to check a few possibilities. We know the following basic rules from arithmetic.

a. The sum of 2 numbers that are divisible by 3 is itself divisible by 3. b. The difference of 2 numbers divisible by 3 is itself divisible by 3.

For transition 5, the large jug either goes to 0, which is divisible by 3, or by x + y - 9, which by rules a and b above, is also divisible by 3. For the small jug, it either goes to 9, or to x + y, which again by rule a, is divisible by 3. The same argument applies to transition 6.

What we’ve proven now is that if we're in a state (x, y) where x and y are both divisible by 3, then we can only transition into states where that is still true. Because the initial state, (0, 0) has both amounts divisible by 3, this shows that it is impossible for the amounts to ever "escape" from being divisible by 3.

To measure 4 litres of water, we’d need to get into (0, 4) or (4, 0). However, the property doesn’t hold for either of these states; therefore, they’re unreachable. This proves that the problem cannot be solved, and the proof is finished.

NB: A common misconception here would be to argue that we can’t assume that the divisible by 3 property holds for (x, y). This is an excellent example of implication in action. We don’t care what happens if they aren’t. What we’re showing is that if they already are, then they are afterwards as well. So given that our property holds for the initial state, we've shown the amounts can't escape that property.

Closing thoughts on mathematics for computer science

My next goals are to complete mathematics for computer science and then do any parts of the following algorithm course that I’m not already familiar with. I also need to see what else is on MIT's OpenCourseWare.

Conclusion

So there you have it. This is how I re-discovered my childhood passion for math, using online resources. I hope it’s helpful to somebody!

If you’re a teacher in math, please know that I don’t think math teachers are bad. Math is one of the toughest subjects to teach (along with physics), and understanding what’s going on in 30 different heads (for a school teacher) or 1000 different heads (for a university lecturer) is pretty much impossible. The main thing I’d like to see teachers do, though is to pay a little more attention to some of the common tripping points and give those a little more attention. These include exponents, rearranging formulae, logarithms and trigonometry. A tool like Khan Academy is great for identifying knowledge gaps in learners and remediating them. For motivated learners, just suggesting that they go on Khan Academy and do this might be enough.

If anybody knows any other resources I might be interested; please do let me know!

Your thoughts

In order to post, you'll need to log in.

Dan Smith says...

Wonderful post!

I think there might be a small typo though. In the last sentence of the paragraph explaining logical implication, don't you mean to say this?

"If it is ever possible for a to be true, but b to be false, then it is not a valid implication."

Or perhaps I'm just misunderstanding the intent of this sentence.

In any case I'm very much looking forward to reading more of your blog, which I only just discovered!

Heidi Newton says...

Sorry for being so slow to approve and respond! Thanks for your kind words :)

I think the sentence you're referring to is this one?

"This illustrates that if a then b does not always mean if b then a, like many students, I included in university, think it must."

I think it's correct as is, but probably a bit confusing. What I was trying to say is that just because a -> b is true, does not necessarily mean that b -> a is also true.