Title image: Euclid’s Elements

Proving various results in math is arguably one of the most rewarding parts of doing it. It’s also very useful in more advanced study because it allows you to definitively assert the truth of a particular statement. In this article, we will go through some insightful mathematical proof methods, and then provide some problems at the end!

Example 1 (Direct Proof): Prove $n(n+1)(n+2)$ is always divisible by 3

At this point, you might be clueless. Or you might be thinking about adding up the digits to see if they are a multiple of 3, as the usual trick goes. However, we don’t know anything about digits here. All we have is these three consecutive integers, so let’s just think about the different cases.

1. $n$ is a multiple of 3
1. We are done as then the whole product is a multiple of 3
2. $n$ is one more than a multiple of 3
1. This means that $n+1$ is two more than a multiple of three and $n+2$ is three more than a multiple of 3, and so is a multiple of 3
3. $n$ is two more than a multiple of 3
1. This means that $n+1$ is 3 more than a multiple of 3, and so a multiple of 3

We see that these are the only cases because three more than a multiple of 3 is a multiple of 3, and so the cycle starts all over again (if you’re interested, this cyclical behavior is an example of modular arithmetic).  Therefore, we have established that no matter what $n$ is, the expression is always a multiple of 3, and so always divisible.

Example 2 (Proof by Contradiction): Prove that $\sqrt{2}$ is irrational (i.e. cannot be expressed in the form $\frac{a}{b}$, where a and b are integers.

The core of this proof method involves assuming that what you want to prove is false, and then showing that this means that one of the original assumptions you made cannot be true. Therefore, the statement cannot be false, so it must be true.

So, let’s try to write $\sqrt{2} = \frac{a}{b}$, and let’s also stipulate that the fraction is in lowest terms (if it’s not, we can just cancel it down until a and b are coprime). Now, let’s square both sides:

$2 = \frac{a^2}{b^2} \Rightarrow 2b^2 = a^2\\$

This means that 2 divides $a^2$, meaning that 2 divides $a$, so $a$ is even. Therefore, let’s write it as $a = 2k$, for some integer $k$, and plug this back in to get:

$2b^2 = a^2 = (2k)^2 = 4k^2\\$

Therefore, if we divide both sides by 2, we get:

$b^2 = 2k^2\\$

Meaning that 2 divides $b^2$, and so 2 divides $b$. So, 2 divides both $a$ and $b$, but wait a minute, we said in our initial assumptions that the fraction $\frac{a}{b}$ was in lowest terms, with $a$ and $b$ coprime. Therefore, we have proven one of our initial assumptions false, meaning that in fact $\sqrt{2}$ cannot be rational (i.e. expressed as a fraction), meaning that it must be irrational.

Example 3 (Proof by Induction): Prove that $1+2+3+...+n = \frac{n(n+1)}{2}$ for all natural numbers $n$.

First, let’s note that natural numbers are positive integers to clarify the problem statement. Now, let’s get familiar with the problem – we try some small cases and see that it is indeed true:

$1+2+3 = 6 = \frac{3(4)}{2} \\$ $1+2+3+4= 10 = \frac{4(5)}{2} \\$ $1+2+3+4+5= 15 = \frac{5(6)}{2}\\$

So, we can see that it works, but we still haven’t really figured out how to prove it, or have we? With the above cases, we see that given a sum up to $n$, to get to the next one, we add $n+1$, so what if we try this more generally? This leads to a proof by induction.

A proof by induction involves proving that a particular statement is true for a ‘base case’, i.e. the smallest number $n$ for which the statement needs to be true (in our case $n=1$). Then, what makes it all work is the ‘inductive hypothesis’. You assume that the statement is true for $n=k$, where $k$ is some natural number (in this case), and then you show that this implies that the statement must be true for $n=k+1$. Therefore, if the statement is true for $n=1$, it must be true for $n=2$, and if it’s true for $n=2$, it must be true for $n=3$, etc. And in this way, the statement becomes true for all numbers you wish to show it’s true for (usually natural numbers). You can think of it like a chain of dominoes falling – all it takes is for them to be arranged close together and for you to knock down the first one.

So, the ‘base case’, is $n=1$, so we check that the statement is true for $n=1$. Sure enough, we get:

$1= \frac{1(2)}{2}\\$

Now, we go with the inductive hypothesis. Let’s assume that

$1+2+3+4 +... +k=\frac{k(k+1)}{2}\\$

And we want to prove:

$1+2+3+4 +... +k+(k+1)=\frac{(k+1)(k+2)}{2}\\$

So let’s just add $k+1$ to the first sum, and try and get it to look like the second one!

$1+2+3+4 +... +k+(k+1)=\frac{k(k+1)}{2} + k+1 = \frac{k(k+1) +2(k+1)}{2} = \frac{(k+1)(k+2)}{2} \\$

Which is exactly what we wanted (with a little bit of factorization)!

Example 4 (Finding an example/counterexample): Does $x^2 + y^2 + z^2 = w^2$ have any solutions when $x,y,z,w$ are all integers?

This final method is nothing fancy – it just involves providing an example, in this case, to answer the statement, in other cases, to show that the statement is false. It just involves some experimentation, so let’s get started! I’ll leave this to you, as there is nothing you do not already know that’s required to solve this. Some hints are difference of two squares factorization, and trying values!

Problems:

1. Prove that given 5 consecutive numbers, at least one of them is divisible by 5.
2. Prove that given 7 consecutive numbers, at least one of them is divisible by 7
3. Prove that $\sqrt{3}$ is irrational
4. Prove that given $k$ consecutive numbers, at least one of them is divisible by $k$
5. Prove that $\sqrt[3]{7}$ is irrational
6. Try to prove that $\sqrt{4}$ is irrational. What happens which means you can’t?
7. Experiment and try to find a formula for the sum of consecutive squares starting from $1^2$. Then, try and prove it using induction!
8. Is $n^2+n+41$ always a prime number? (Hint: experiment!)
9. Find an expression for $2^0 + 2^1 + 2^2 + ... + 2^{n-1}$
10. Can you find something similar for sums of powers of 3?