# Math

I use this tag for when the topic is about pure math. So whenever I dive into proofs, explanations of math topics or news on the research this is where you should look.

## Reverse Polish Notation

One of the most popular pages on mathblog is the infix to postfix converter. When I realized that –  I decided it was worth diving a little more into what postfix or Reverse Polish Notation as it is better known is. Reverse Polish Notation is a mathematical notation which is functioning very well in a stack based implementation. In Reverse Polish Notation the operators follow their operands, in contrast to Polish Notation, in which operators precede their operands. One of the main benefits of Reverse Polish Notation is the fact that it does not rely on parentheses to evaluate the expression – as long as each operator has a  fixed number of operands. Continue reading →

Posted by in Math, 0 comments

## Making decisions under uncertainty in everyday life

Everyday I (and probably everyone else) am faced with decisions that we have to make, some of them are small, some of them are big.  At least for me there are two aspects governing the decisions I want to make. I want to make the best decision and I am making the decisions without knowing everything.  This is exactly what stochastic optimization and what I work with in my daily job.

But now I have found a really good example from real life which I am facing often and which have some really interesting characteristics. It involves something I know that several people have been thinking about when walking in a city: How can we come from point A to point B in the most effective way.

I wont be getting into details of how to formulate any of this in a mathematical setting. You can find lots of text books on that. I just want to introduce you to some of the concepts and ideas of it. Continue reading →

Posted by in Math, 2 comments

## News on the ABC conjecture

Here is some news of the possible breakthrough of the ABC conjecture. It  might already be commonly known, but  it is something I only recently discovered was going on. There are rumors that Shinichi Mochizuki from Kyoto university has solved the abc conjecture. You can find his proof here. Not that I understood anything of it, but I though a link would be appropriate. But don’t despair yet, I will have a few more links in this regard. Continue reading →

Posted by in Math, 0 comments

## Pandigitial primes

I got a fun little question from Jean-Marie by email the other day. With the disclaimer that I don’t really have the time to solve that many puzzles and therefore probably wont be able to give you a solution to puzzles like this one. This one triggered my curiosity and I managed to find a rather cure solution.

Therefore I will post it to you all and let you wonder a bit about it. If you find the solution feel free to post it in the comments.

The question is simple:

Find all the primes that contain 9 different digits (0 excluded).

Good luck 🙂

Posted by in Math, 3 comments

## Proving the fundamental lemma of Arithmetic

Last time I blogged I wrote about why proofs are so difficult. This time we should try to prove something a little more complicated and see if we can get some of the thoughts behind the proof while doing it to see if it really requires that amount of insights or part of a proof can be done by using more or less common sense. My guess is that we can come far with common sense, but we at some point need to rely on some insights or methods we have seen before. Continue reading →

Posted by in Math, 0 comments

## Why are proofs so frustrating?

I have often been sitting there swearing when I couldn’t figure out to how to prove something and I know for certain I am not the only one. But why are proofs so difficult when they seem so easy when you read them? This post is about the softer side of proofs, to encourage you to not loose faith when you meet something you can’t prove. Continue reading →

Posted by in Math, 0 comments

## A Short Treatise on a Vectors Concept

I have been in contact with Frederick Koh from Whitegroupmaths.com who kindly agreed that he would write a guest post for the blog to promote what he has to offer – Tutoring in A level maths in Singapore.  So without further ado let me present you with the real content.

I have been asked on numerous occasions by students to provide a short effective mathematical proof verifying the fact that obtaining the vector product of the normals characterising two separate non parallel planes in 3 dimensional Cartesian space produces the direction vector of the line arising from the intersection of the above mentioned planes. I shall share this here:

(Note that the reader is assumed to possess knowledge of basic scalar and vector product operations) Continue reading →

Posted by in Math, 1 comment

## The pigeon hole principle

The pigeon hole principle is a counting argument stating something as simple as “if you have n items which are to be put into m < n boxes then there is at least 2 items in one of the boxes”. My first comment on that was “well duh!”, that is obvious, but it can actually be used to prove some less intuitive things.

So an example if you have 10 balls which are to be put into 9 boxes then at least 1 of the boxes contains at least 2 balls (unless you drop one of them…). But what can we use it for. I will show one of my favourite examples of it which I do not find intuitive at first glance. Continue reading →

Posted by in Math, 0 comments

## Proof method: Multidimensional induction

For the last couple of posts we have been dealing with mathematical induction. This post shall be no different. However, until now we have been limited to one variable, so this post will deal with induction on multiple variables – or in other words multidimensional induction as the headline suggests. I will treat the two dimensional case in this post, but the expansion to n dimensions should be relatively easy. So for now we will assume that we have a statement P(m,n) which we need to prove.

If we have the statement P(m,n) then we need to prove three things:

1. Basecase: We need to prove a base case P(a,b) where a is the smallest value for which m is valid and b is the smallest value where n is valid.
2. Induction over m: We assume that P(k,b) is valid for some positive integer k. Then we need to prove that P(k+1,b) is valid.
3. Induction over n: We assume that P(h,k) is valid for some positive integers h,k. Then we need to prove that P(h,k+1) is valid.

If we can prove these three things then we have proved that P(m,n) is true for all and . point 1 and 2 ensures that the statement is true for all P(m,a) just as in the in the single variable case. Once we have proven that then adding 3 ensures that it holds for all n as well. But let us take an example. Continue reading →

Posted by in Math, 4 comments

## Proof method: Strong Induction

As I promised in the Proof by induction post, I would follow up to elaborate on the proof by induction topic. Here is part of the follow up, known as the proof by strong induction.  What I covered last time, is sometimes also known as weak induction.

In weak induction the induction step goes:

Induction step: If P(k) is true then  P(k+1) is true as well.

Strong induction expands the concept to:

Induction step: If P(m), P(m+1), P(m+2)… P(k) is true then  P(k+1) is true as well for some k > m.

The difference between the two methods is what assumptions we need to make in the induction step. To switch to the metaphor of dominoes again – in the weak induction we need to know that the previous domino is toppled, then the next one will topple as well. In strong induction we need to know that all the previous ones has toppled before we can ensure that the next one will fall as well.

Both methods have the same logical strength when we apply them, since in order to get to the k’th domino we need to topple 1,2,3,…k-1 anyway. However, sometimes strong induction makes the proof of the induction step easier.

## Strong Induction Example 1

I have shamelessly stolen this example from Hammack since I think it brilliantly shows when strong induction is better to use. But lets first see what happens if we try to use weak induction on the following:

Proposition: if , then 12|(n4 – n2)

### Weak induction

Base case: we need to prove that 12|(14 – 12) = 12|(1- 1) = 0, which is divisible by 12 by definition.

Induction step: We assume that the 12|(k4 – k2) is true such that (n4 – n2) = 12a for some . We then need to show that ((k+1)4 – (k+1)2) = 12b for some .

My approach would be to a direct proof such that

(k+1)4 – (k+1)2 = k4 + 4k3 + 6k2 + 4k + 1 – (k2 + 2k + 1) =  (k4 – k2) + 4k3 + 6k2 + 2k = 12a + 4k3 + 6k2 + 2k

How do we proceed from there? I don’t have a clue. If you can show me how to continue of this road I would be glad to hear it.

### Strong induction

The weak induction method failed. However, we can show that n = k-5 implies that the statement is true for k+1, so we need to expand the base case to include everything up to n = 6.

Base case:
n = 1:  12|(14 – 12) = 12|(1- 1) = 0 = 012
n = 2:  12|(24 – 22) = 12|16-12 = 12 = 1
12
n = 3:  12|(34 – 32) = 12|(81 – 9) = 72  = 612
n = 4:  12|(44 – 42) = 12|(256- 16) = 240 = 20 * 12
n = 5:  12|(54 – 52) = 12|(625- 25) = 600 = 50
12
n = 6:  12|(64 – 62) = 12|(1296- 36) = 1260 = 105*12

So far it fits really well.

Induction step: let and assume that 12|(m4 – m2) for , now we need to prove that 12|((k+1)4 – (k+1)2)  is true as well.

Let us define l =  k-5 for which we assume the proposition to be true such that  (l4 -l2) = 12a for some value of a. We need to show that 12|((l+6)4 – (l+6)2) is true.  So let us try with a direct approach

(l+6)4 – (l+6)2= (l4 +24l3 + 180l2 + 864l + 1296) – (l2 + 12l + 36) = (l4 – l2) +24l3 + 180l2 + 852l + 1260 = 12a +12(2l3 + 15l2 + 71l + 105).

This statement is clearly divisible by 12, and thus proofs the proposition.

QED

So in order to prove it for n = k+1 = 7 we need n = k-5 = 1 to prove it, but that is handled in the base case, same goes for all the n = 8,9,10,11,12 and then we start to rely on the fact that we can prove n= 8 through the induction step.

Image Credits

The metaphor of dominoes also gave rise to the chosen post photo, which was kindly shared under the creative common license by Malkav. My crop of the photo is of course shared under the same conditions.

Posted by in Math, 15 comments