Proving theorems and special cases (Part 6): The Goldbach conjecture

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no. In this series of posts, we’ve already seen that a conjecture could be true for the first 40 cases or even the first $10^{316}$ cases yet ultimately prove false for all cases.

For the next few posts, I thought I’d share a few of the most famous unsolved problems in mathematics… and just how much computational work has been done to check for a counterexample.

1. The Goldbach conjecture (see here and here for more information) claims that every even integer greater than 4 can be written as the sum of two prime numbers. For example,

4 = 2 + 2,

6 = 3 + 3,

8 = 3 + 5,

10 = 3 + 7,

12 = 5 + 7,

14 = 3 + 11, etc.

This has been verified for all even numbers less than $4 \times 10^{18} = 4,000,000,000,000,000,000$ . A proof for all even numbers, however, has not been found yet.

Here are some results related to the Goldbach conjecture that are known:

1. Any integer greater than 4 is the sum of at most six primes.

2. Every sufficiently large even number can be written as the sum or two primes or the sum of a prime and the product of two primes.

3. Every sufficiently large even number can be written as the sum of two primes and at most 8 powers of 2.

4. Every sufficiently large odd number can be written as the sum of three primes.

Proving theorems and special cases (Part 5): Mathematical induction

Today’s post is a little bit off the main topic of this series of posts… but I wanted to give some pedagogical thoughts on yesterday’s post concerning the following proof by induction.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$ .

$n = 1$ : $5^1 - 1 = 4$ , which is clearly a multiple of 4.

$n$ : Assume that $5^n - 1$ is a multiple of 4, so that $5^n - 1 = 4q$ , where $q$ is an integer. We can also write this as $5^n = 4q + 1$ .

$n+1$ . We wish to show that $5^{n+1} - 1$ is equal to $4Q$ for some (different) integer $Q$ . To do this, notice that

$5^{n+1} - 1 = 5^1 5^n - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$ .

So if we let $Q = 5q +1$ , then $5^{n+1} - 1 = 4Q$ , where $Q$ is an integer because $q$ is also an integer.

My primary observation is that even very strong math students tend to have a weak spot when it comes to simplifying exponential expressions (as opposed to polynomial expressions). For example, I find that even very good math students can struggle through the logic of this sequence of equalities:

$2^n + 2^n = 2 \times 2^n = 2^1 \times 2^n = 2^{n+1}$ .

The first step is using the main stumbling block. Students who are completely comfortable with simplifying $x + x$ as $2x$ can be perplexed by simplifying $2^n + 2^n$ as $2 \times 2^n$ . I attribute this to lack of practice with this kind of simplification in lower grade levels.

Here’s another algoebraic stumbling block that I’ve often seen: at the beginning of the $n+1$ case, some students will make the following mistake:

$5^{n+1} - 1 = 5^1 5^n - 1 = 5 (4q) = 4 (5q) = 4Q$ .

Because these students end with a multiple of 4, they fail to notice that the second equality is incorrect since

$5^1 5^n - 1 \ne 5^1 (5^n - 1)$ .

Again, I attribute this to lack of practice with simplifying exponential expressions in lower grade levels… as well as being a little bit over-excited upon seeing $5^n - 1$ and wishing to use the induction hypothesis as soon as possible.

Proving theorems and special cases (Part 4): Mathematical induction

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct. In the previous two posts, we saw that a statement that’s true for the first 40 cases or even the first $10^{316}$ cases may not be true for all cases.

This is the reason that mathematical induction is important, as it provides a way to build from previous cases to prove that the next case is still correct, thus proving that all cases are correct.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$ .

$n = 1$ : $5^1 - 1 = 4$ , which is clearly a multiple of 4.

$n$ : Assume that $5^n - 1$ is a multiple of 4, so that $5^n - 1 = 4q$ , where $q$ is an integer. We can also write this as $5^n = 4q + 1$ .

$n+1$ . We wish to show that $5^{n+1} - 1$ is equal to $4Q$ for some (different) integer $Q$ . To do this, notice that

$5^{n+1} - 1 = 5^n 5^1 - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$ .

So if we let $Q = 5q +1$ , then $5^{n+1} - 1 = 4Q$ , where $Q$ is an integer because $q$ is also an integer.

QED

In the above proof, we were able to build from the $n$ case to reach the $n +1$ case. In this sense, to answer the student’s question, it is possible to prove a theorem by first proving a special case of the theorem.

By contrast, when trying to “prove” that $n^2 - n + 41$ is prime for all integers $n$ , the proposition is true for $1 \le n \le 40$ , but it’s just a coincidence… there was no string of logic that connected these first 40 cases other than the coincidence that they all were correct.

Proving theorems and special cases (Part 3): Skewes’ number

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

In the first two posts of this series, we showed conjectures could be true for the first 40 cases or even the first 900 million odd cases but fail on the next case. In today’s post, I’ll describe a conjecture that, for hundreds of years, was thought to be true for all integers $n$ and has since been shown to be true for all $n \le 10^{316}$ . However, despite being true for so many special cases, the conjecture is false.

Let’s absorb the above paragraph again. The conjecture “ $n^2 - n + 41$ is always prime” was true for the first 40 cases before failing. By contrast, the conjecture I’m about the describe is true for the first (approximately) 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000 cases before failing.

The conjecture in question concerns the number of prime numbers $\pi(n)$ that are less than or equal to $n$ . For example:

There are four prime numbers less than 10 (namely 2, 3, 5, 7), and so $\pi(10) = 4$ .

There are eight prime numbers less than 10 (namely 2, 3, 5, 7, 11, 13, 17, 19), and so $\pi(20) = 8$ .

One of the classic problems in mathematics, often called the Prime Number Theorem, is estimating the value of $\pi(n)$ when $n$ is large. It turns out that one way of approximating $\pi(n)$ is through the logarithmic integral

$\hbox{Li}(n) = \displaystyle \int_2^n \frac{dx}{\ln x}$

Indeed, the Prime Number Theorem states that

$\pi(n) \sim \hbox{Li}(n)$ ,

$\displaystyle \lim_{n \to \infty} \frac{\pi(n)}{\hbox{Li}(n)} = 1$ .

This asymptotic relationship was proven by the eminent mathematician Karl Friedrich Gauss.

With that as prelude, here’s the false conjecture. For decades, luminaries of mathematics, including Gauss and Bernhard Riemann, conjectured that

$\pi(n) < \hbox{Li}(n)$ for all integers $n$

based on the available numerical evidence at the time. However, this conjecture was proven false in the 20th century by the British mathematician John Littlewood. No only did Littlewood show that there is a value of $n$ so that $\pi(n) > \hbox{Li}(n)$ , but he also showed that the graphs of $\pi(n)$ and $\hbox{Li}(n)$ cross over each other infinitely many times!

Littlewood proved his theorem over 100 years ago in 1914. Today, even with modern computing power, we still do not precisely know the first value of $n$ for which $\pi(n) > \hbox{Li}(n)$ . This number is called Skewes’ number, in honor of the mathematician who first found (in 1955) an upper bound on this first crossing point. The bound that he found was absolutely enormous: he showed that $\pi(n) > \hbox{Li}(n)$ for some $n$ less than

$\displaystyle 10^{\displaystyle 10^{10^{34}}}$

More recent work has established that the first crossover likely occurs in the vicinity of $n \approx 1.397 \times 10^{316}$ .

Whoever first evaluates Skewes’ number exactly will surely have a nice feather in his/her cap for completing a task that mystified both Gauss and Riemann.

References:

http://mathworld.wolfram.com/PrimeNumberTheorem.html

http://mathworld.wolfram.com/SkewesNumber.html

http://mathworld.wolfram.com/PrimeCountingFunction.html

http://mathworld.wolfram.com/LogarithmicIntegral.html

Proving theorems and special cases (Part 2): The Pólya conjecture

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

In yesterday’s post, we showed that the conjecture “ $n^2 - n + 41$ is a prime number for all positive integers $n$ ” is true for $1 \le n \le 40$ but fails for $n = 41$ . In today’s post, I’ll describe a conjecture that is true for plenty more special cases before becoming false.

The Pólya conjecture (see here and here for more information) stated that 50% or more of the natural numbers less than or equal to any given number have an odd number of prime factors (counting multiplicity). For example:

$2$ has one prime factor: odd

$3$ has one prime factor: odd

$4 = 2 \times 2$ has two prime factors: even

$5$ has one prime factor: odd

$6 = 2 \times 3$ has two prime factors: even

$7$ has one prime factor: odd

$8 = 2 \times 2 \times 2$ has three prime factors: odd

$9 = 3 \times 3$ has two prime factors: even

$10 = 2 \times 5$ has two prime factors: even

So of the numbers less than or equal to 10, five have an odd number of prime factors, and only four have an even number of prime factors.

The Pólya conjecture was first proven false by producing a counterexample in the vicinity of $1.845 \times 10^{361}$ . It turns out that the smallest counterexample is 906,150,257. In other words, the Pólya conjecture is true for the first 906,150,256 cases but fails on the next case.

Proving theorems and special cases (Part 1): Is n^2-n+41 always prime?

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

The following example probably appears in every textbook that I’ve seen that handles mathematical induction to convince students that checking even many special cases of a conjecture is not sufficient for proving the conjecture.

Conjecture: If $n \ge 1$ is a positive integer, then $n^2 - n + 41$ is a prime number.

Is this true? Well, let’s start checking:

If $n = 1$ , then $n^2 - n + 41 = 1^2 - 1 + 41 = 41$ , which is a prime number.

If $n = 2$ , then $n^2 - n + 41 = 2^2 - 2 + 41 = 43$ , which is a prime number.

If $n = 3$ , then $n^2 - n + 41 = 3^2 - 3 + 41 = 47$ , which is a prime number.

If $n = 4$ , then $n^2 - n + 41 = 4^2 - 4 + 41 = 53$ , which is a prime number.

If $n = 5$ , then $n^2 - n + 41 = 5^2 - 5 + 41 = 61$ , which is a prime number.

If $n = 6$ , then $n^2 - n + 41 = 6^2 - 6 + 41 = 71$ , which is a prime number.

If $n = 7$ , then $n^2 - n + 41 = 7^2 - 7 + 41 = 83$ , which is a prime number.

If $n = 8$ , then $n^2 - n + 41 = 8^2 - 8 + 41 = 97$ , which is a prime number.

If $n = 9$ , then $n^2 - n + 41 = 9^2 - 9 + 41 = 113$ , which is a prime number.

If $n = 10$ , then $n^2 - n + 41 = 10^2 - 10 + 41 = 131$ , which is a prime number.

If $n = 11$ , then $n^2 - n + 41 = 11^2 - 11 + 41 = 151$ , which is a prime number.

If $n = 12$ , then $n^2 - n + 41 = 12^2 - 12 + 41 = 173$ , which is a prime number.

If $n = 13$ , then $n^2 - n + 41 = 13^2 - 13 + 41 = 197$ , which is a prime number.

If $n = 14$ , then $n^2 - n + 41 = 14^2 - 14 + 41 = 223$ , which is a prime number.

If $n = 15$ , then $n^2 - n + 41 = 15^2 - 15 + 41 = 251$ , which is a prime number.

If $n = 16$ , then $n^2 - n + 41 = 16^2 - 16 + 41 = 281$ , which is a prime number.

If $n = 17$ , then $n^2 - n + 41 = 17^2 - 17 + 41 = 313$ , which is a prime number.

If $n = 18$ , then $n^2 - n + 41 = 18^2 - 18 + 41 = 347$ , which is a prime number.

If $n = 19$ , then $n^2 - n + 41 = 19^2 - 19 + 41 = 383$ , which is a prime number.

If $n = 20$ , then $n^2 - n + 41 = 20^2 - 20 + 41 = 421$ , which is a prime number.

If $n = 21$ , then $n^2 - n + 41 = 21^2 - 21 + 41 = 461$ , which is a prime number.

If $n = 22$ , then $n^2 - n + 41 = 22^2 - 22 + 41 = 503$ , which is a prime number.

If $n = 23$ , then $n^2 - n + 41 = 23^2 - 23 + 41 = 547$ , which is a prime number.

If $n = 24$ , then $n^2 - n + 41 = 24^2 - 24 + 41 = 593$ , which is a prime number.

If $n = 25$ , then $n^2 - n + 41 = 25^2 - 25 + 41 = 641$ , which is a prime number.

If $n = 26$ , then $n^2 - n + 41 = 26^2 - 26 + 41 = 691$ , which is a prime number.

If $n = 27$ , then $n^2 - n + 41 = 27^2 - 27 + 41 = 743$ , which is a prime number.

If $n = 28$ , then $n^2 - n + 41 = 28^2 - 28 + 41 = 797$ , which is a prime number.

If $n = 29$ , then $n^2 - n + 41 = 29^2 - 29 + 41 = 853$ , which is a prime number.

If $n = 30$ , then $n^2 - n + 41 = 30^2 - 30 + 41 = 911$ , which is a prime number.

If $n = 31$ , then $n^2 - n + 41 = 31^2 - 31 + 41 = 971$ , which is a prime number.

If $n = 32$ , then $n^2 - n + 41 = 32^2 - 32 + 41 = 1033$ , which is a prime number.

If $n = 33$ , then $n^2 - n + 41 = 33^2 - 33 + 41 = 1097$ , which is a prime number.

If $n = 34$ , then $n^2 - n + 41 = 34^2 - 34 + 41 = 1163$ , which is a prime number.

If $n = 35$ , then $n^2 - n + 41 = 35^2 - 35 + 41 = 1231$ , which is a prime number.

If $n = 36$ , then $n^2 - n + 41 = 36^2 - 36 + 41 = 1301$ , which is a prime number.

If $n = 37$ , then $n^2 - n + 41 = 37^2 - 37 + 41 = 1373$ , which is a prime number.

If $n = 38$ , then $n^2 - n + 41 = 38^2 - 38 + 41 = 1447$ , which is a prime number.

If $n = 39$ , then $n^2 - n + 41 = 39^2 - 39 + 41 = 1523$ , which is a prime number.

If $n = 40$ , then $n^2 - n + 41 = 40^2 - 40 + 41 = 1601$ , which is a prime number.

Okay, a show of hands… did anyone actually carefully read and check the above 40 lines? I didn’t think so. The point is that the proposition works for $n = 1, 2, 3, \dots, 40$ . By about $n = 4$ , or so, a student (who didn’t already know the answer) actually did the above work would begin thinking, “Wow, this probably is correct for any value of $n$ .”

Of course, the catch happens at $n = 41$ :

If latex n = 41, then $n^2 - n + 41 = 41^2 - 41 + 41 = 41^2 = 41 \times 41$ ,

which is not a prime number.

All this to say, seeing a trend for the first few special cases… or the first few dozen special cases… does not necessarily mean that the trend will continue.

Interesting calculus problems

Source: http://xkcd.com/135/

Engaging students: Completing the square

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission again comes from my former student Tracy Leeper. Her topic, from Algebra: completing the square.

What interesting things can you say about the people who contributed to the discovery and/or the development of this topic?

Muhammad ibn Musa al-Khwarizmi wrote a book called al-jabr in approximately 825 A.D. He was in Babylon and he worked as a scholar at the House of Wisdom. Al-Khwarizmi had already mastered Euclid’s Elements, which is the foundation for Geometry. So in his book he posed the challenge “What must be the square which, when increased by ten of its own roots; amounts to 39?” or in other words: how to solve he turned to geometry and drew a picture to figure out the answer. By doing so, al-Khwarizmi found out how to solve equations by completing the square. He also included instructions on how he solved the problem in words. His book al-jabr become the foundation for our modern day algebra. The Arabic word al-jabr was translated into Latin to give us algebra, and our word for algorithm came from al-Khwarizmi, if you can believe it. Later on, his work was used by other Arab and Renaissance Italian mathematicians to “complete the cube” for solving cubic equations.

How does this topic extend what your students should have learned in previous courses?

In previous courses my students should have already been introduced to prime factorization, the quadratic formula, parabolas, coordinates graphs and other similar topics. Completing the square is another way for students to find the roots of a quadratic equation. The first way taught is by using nice numbers that will factor easily. Then the math progresses to using the quadratic equation for the numbers that don’t factor easily. Completing the square is just another way to solve a quadratic that does not easily factor. Some students prefer to go straight to the quadratic equation, whereas other students will favor completing the square after they learn how to do it. It gives the students another “tool” for their toolbox on how to solve equations, and will enable them to solve equations that previously were unsolvable, such as the quadratic . By giving students a variety of ways to solve a problem, they can pick whichever way they are most comfortable with, which in turn will boost their confidence in their ability to learn math.

How could you as a teacher create an activity or project that involves your topic?

Usually the simplest way to learn something is to see something concrete of what you are trying to do. For completing the square, I can give the students the procedure to follow, but they probably won’t be able to fully understand why it works. In order to help them visualize it, I would use algebra tiles. One long tile is equal to x, since its length is x and its width is 1. The square is equal to since the length and the width are both equal to x. However, when you try to add to the square by a factor of x, you end up having a corner missing. This is the part that is missing from the initial equation. Then the students see that you don’t have a complete square, but by adding the same amount to both parts, we can get a complete square that can then be factored. Like so…

References:

http://bulldog2.redlands.edu/fac/beery/math115/m115_activ_complsq.htm

http://www.youtube.com/watch?v=JXrj5Dtgpss

Engaging students: Graphing parabolas

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission again comes from my former student Tiffany Wilhoit. Her topic, from Algebra: graphing parabolas.

How did people’s conception of this topic change over time?

The parabola has been around for a long time! Menaechmus (380 BC-320 BC) was likely the first person to have found the parabola. Therefore, the parabola has been around since the ancient Greek times. However, it wasn’t until around a century later that Apollonius gave the parabola its name. Pappus (290-350) is the mathematician who discovered the focus and directrix of the parabola, and their given relation. One of the most famous mathematicians to contribute to the study of parabolas was Galileo. He determined that objects falling due to gravity fall in parabolic pathways, since gravity has a constant acceleration. Later, in the 17^th century, many mathematicians studied properties of the parabola. Gregory and Newton discovered that parabolas cause rays of light to meet at a focus. While Newton opted out of using parabolic mirrors for his first telescope, most modern reflecting telescopes use them. Mathematicians have been studying parabolas for thousands of years, and have discovered many interesting properties of the parabola.

How could you as a teacher create an activity or project that involves your topic?

A fun activity to set up for your students will include several boxes and balls, for a smaller set up, you can use solo cups and ping pong balls. Divide the class into groups, and give each group a set of boxes and balls. First, have the students set up a tower(s) with the boxes. The students will now attempt to knock the boxes down using the balls. The students can map out the parabolic curve showing the path they want to take. By changing the distance from the student throwing the ball and the boxes, the students will be able to see how the curve changes. If students have the tendency to throw the ball straight instead of in the shape of a parabola, have a member of the group stand between the thrower and the boxes. This will force the ball to be thrown over the student’s head, resulting in the parabolic curve. The students can also see what happens to the curve depending on where the student stands between the thrower and boxes. In order for the students to make a positive parabolic curve, have them throw the ball underhanded. This activity will engage the students by getting them involved and active, plus they will have some fun too! (To start off with, you can show the video from part E1, since the students are playing a real life version of Angry Birds!)

How can technology be used to effectively engage students with this topic?

A great video to show students before studying parabolas can be found on YouTube:

The video uses the popular game Angry Birds to introduce parabolic graphs. First, the video shows the bird flying a parabolic path, but the bird misses the pig. The video goes on to explain why the pig can’t be hit. It does a good job of explaining what a parabola is, why the first parabolic curve would not allow the bird to hit the pig, and how to change the curve to line up the path of the bird to the pig. This video would be interesting to the students, because a majority of the class (if not all) will know the game, and most have played the game! The video goes even further by encouraging students to look for parabolas in their lives. It even gives other examples such as arches and basketball. This will get the students thinking about parabolas outside of the classroom. (This video would be perfect to show before the students try their own version of Angry Birds discussed in part A2)

Resources:

Youtube.com/watch?v=bsYLPIXI7VQ

Parabolaonline.tripod.com/history.html

http://www-history.mcs.st-and.ac.uk/Curves/Parabola.html

Preparation for Industrial Careers in the Mathematical Sciences: Finding the Safest Place to Store Nuclear Waste

The Mathematical Association of America recently published a number of promotional videos showing various mathematics can be used in “the real world.” Here’s the first pair of videos describing the process of mathematical modeling. From the YouTube descriptions:

Dr. Genetha Gray talks about her path and about a research problem that she worked on at Sandia National Laboratories. Using quite limited geological data, they had to create a groundwater flow computational model, with parameters to be determined, so that they could study the feasibility and safety of prospective subsurface nuclear waste storage sites.

Prof. Gwen Spencer of Smith College introduces the mathematics behind optimization, calibration, and the quantification of uncertainty in models and in the results that they give.