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.

Engaging students: Mathematical induction

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 comes from my former student Emily Bruce. Her topic, from Precalculus: mathematical induction.

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

In order to help students understand how induction works, I would either use the domino example or the idea behind an assembly line. Using dominos, students would make a domino train by standing them on their ends close to each other. Students should be able to see that we only have to knock down the first one in order to guarantee that all of them fall over because we know that any one tile falling over will knock over the next one. The assembly line analogy uses the idea that as long as an object begins down the assembly line and each person does their job and passes it on, the object will be made correctly. Like induction, these examples only require us to have the first step succeed and guarantee that it passes from one step to the next, in order to guarantee that it will work for every step.

How can this topic be used in your students’ future courses in mathematics or science?

Induction is a basic proof method that is very useful when proving statements that involve all natural numbers. It is used in pre-calculus, as well as more advanced calculus courses and other upper level college courses. It is an extremely helpful tool when dealing with the natural numbers. Using induction, we can prove conjectures about different series or summations. Knowing and understanding different patterns of with the natural numbers is particularly important in later calculus classes when they focus on the possible convergence of different series and summations.

How has this topic appeared in pop culture?

The movie Titanic is a classic movie about a sinking cruise ship. The question to be posed is “How did they know the whole ship would sink from one hole?” The answer involves induction. The captain would have known that the bulkhead that had a hole would flood completely from the hole. He also would have known that as soon as any one bulkhead was full, another adjacent bulkhead would begin filling up. This is the concept of induction. Using just those two pieces of information, the captain was able to induce that the boat would continue to fill with water until it sank. This is why the captain immediately began evacuating the boat. It was only a matter of time before the ship went down, with everything in it. He knew all of this just form knowing that the first bulkhead would fill and once any one was full, the next would begin to fill as well. The knowledge and quick thinking of the captain saved many lives from the Titanic.

Received from:

http://math.stackexchange.com/questions/423513/how-to-teach-mathematical-induction

Engaging students: Mathematical induction

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

This student submission comes from my former student Michael Dixon. His topic, from Precalculus: mathematical induction.

How can this topic be used in your students’future courses in mathematics or science?

The first time student are introduced to mathematical proofs is probably in high school geometry class, proving theorems using the axiomatic method. They work to prove things about Euclidean geometry with step by step deductive reasoning, as did Euclid himself in the Elements. They prove things about concrete objects that they can see and draw on paper, such as circles, angles, lines, and triangles. But then they move on to Algebra II where they are taught more abstract ways of dealing with numbers and expressions. Is there any way to prove things about numbers themselves? It’s not as easy to visualize, that’s for sure. What is a number? Is it something I can see and feel; is it the shape we write on the page? Or is it something beyond that? This aspect is one of the challenges that algebra students face as they are exposed to more and more mathematics. Mathematical Induction is one way to prove things about numbers using solid deductive reasoning that cannot be refuted. And not just about a few numbers; high school students would be more accepting of that. Mathematical induction is usually used to prove something about ALL of the natural numbers, starting from one and going on out past infinity. Induction can be used to prove what students might intuitively think about the natural numbers, such as that there are an infinite number of primes, or it can be used to prove less obvious things about numbers, such as 1 + 3 + 5 + 7 + …+ n = n². We can prove these and more without having to compute billions and billions of cases. In just a few lines of mathematical logic, we can prove that something is true for every natural integer. This is more than just telling the students something and them accepting it, this technique PROVES that some statements are always true for any number we want to choose, no matter how large it is. That’s some powerful stuff.

How was this topic adopted by the mathematical community.

Mathematical induction has been around for thousands of years. While not in the same form as we see it today, induction can be seen all the way back to Euclid’s proof that there are an infinite number of primes, or in the writings of Aristotle. They used this logic to prove a lot of things, but it was not in the formal way of proving something about n and n + 1. This formal notation did not show up until around 1575, when Maurolycus that 1 + 3 + 5 + 7 + …+ n = n², though he did not prove using n and n + 1, yet. Several mathematicians began using this formal method soon after, such as Pascal and , though no one had a name for it. Bernoulli then was one of the first to begin using the method of arguing from n to n + 1. Since then, mathematicians have been heavily using this method to prove countless things about the natural numbers. And eventually, around the 20th century the name itself, mathematical induction, finally became the standard term for the method starting over two thousand years ago.

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

These videos cover mathematical induction in a way I hadn’t seen before, and cleared up a misconception that I had. I had always thought (because of the name) that mathematical induction was not the same kind of reasoning that is used in other axiomatic proofs. However, mathematical induction happens to actually be deductive reasoning, rather than inductive reasoning. The only similarity is that both mathematical induction and inductive reasoning deal with occurring patterns. The first video is more the engage part, while the second one goes a lithe further into the content. For the engage, showing the video at the beginning of the class is probably better, while the second might be given to the students as homework to watch on their own.

Resources

http://www.onlinemathlearning.com/mathematical-induction.html

http://pballew.blogspot.com/2009/09/mathematical-induction-brief-history-of.html

http://youtu.be/R6U-HXV-17Q

http://youtu.be/JRRMjaarOx4

Exponential growth and decay (Part 5): Paying off credit-card debt via recurrence relations

The following problem in differential equations has a very practical application for anyone who has either (1) taken out a loan to buy a house or a car or (2) is trying to pay off credit card debt. To my surprise, most math majors haven’t thought through the obvious applications of exponential functions as a means of engaging their future students, even though it is directly pertinent to their lives (both the students’ and the teachers’).

You have a balance of $2,000 on your credit card. Interest is compounded continuously with a rate of growth of 25% per year. If you pay the minimum amount of $50 per month (or $600 per year), how long will it take for the balance to be paid?

In previous posts, I approached this problem using differential equations. There’s another way to approach this problem that avoids using calculus that, hypothetically, is within the grasp of talented Precalculus students. Instead of treating this problem as a differential equation, we instead treat it as a first-order difference equation (also called a recurrence relation):

$A_{n+1} = r A_n - k$

The idea is that the amount owed is multiplied by a factor $r$ (which is greater than 1), and from this product the amount paid is deducted. With this approach — and unlike the approach using calculus — the payment period would be each month and not per year. Therefore, we can write

$A_{n+1} = \displaystyle \left( 1 + \frac{0.25}{12} \right) A_n - 50$

Notice that the meaning of the 25% has changed somewhat… it’s no longer the relative rate of growth, as the 25% has been equally divided for the 12 months.

green line A full treatment of the solution of difference equations belongs to a proper course in discrete mathematics. However, this particular difference equation can be solved in a straightforward fashion that should be accessible to talented Precalculus students. Let’s use the above recurrence relation to try to find a pattern. For $n = 1$ , we find

$A_1 = r A_0 - k = r P - k$ .

For $n = 2$ , we find

$A_2 = r A_1 - k$

$A_2 = r (rP - k) - k$

$A_2 = r^2P - rk - k$

$A_2 = r^2 P - k (1 + r)$

For $n = 3$ , we find

$A_3 = r A_2 - k$

$A_3 = r \left[ r^2 P - k(1+r) \right] - k$

$A_3 = r^3 - rk(1+r) - k$

$A_3 = r^3 P - rk - r^2k - k$

$A_3 = r^2 P - k \left( 1 + r+r^2 \right)$

At this point, we can probably guess a pattern:

$A_n = r^n P - k \left( 1 + r + r^2 + \dots + r^{n-1} \right)$

Using the formula for a finite geometric series, this simplifies as

$A_n = r^n P - k \left( \displaystyle \frac{1 - r^n}{1-r} \right)$ .

Indeed, though I won’t do it here, this can be formally proven using mathematical induction.

Fun lecture on geometric series (Part 5): The Fibonacci sequence

Every once in a while, I’ll give a “fun lecture” to my students. The rules of a “fun lecture” are that I talk about some advanced applications of classroom topics, but I won’t hold them responsible for these ideas on homework and on exams. In other words, they can just enjoy the lecture without being responsible for its content.

In this series of posts, I’m describing a fun lecture on generating functions that I’ve given to my Precalculus students. In the previous post, we looked at the famed Fibonacci sequence

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$

We also looked at that (slightly less famous) Quintanilla sequence

$1, 1, 3, 5, 11, 21, 43, 85, \dots$

which is defined so that each term is the sum of the previous term and twice the term that’s two back in the sequence. Using the concept of a generating function, we found that the $n$ th term of the Quintanilla sequence is

$Q_n = \displaystyle \frac{2^{n+1} + (-1)^n}{3}$

To close out the fun lecture, I’ll then verify that this formula works by using mathematical induction. As seen below, it’s a lot less work to verify the formula with mathematical induction than to derive it from the generating function.

$n=0$ : $Q_0 = \displaystyle \frac{2+1}{3} = 1$ .

$n = 1$ : $Q_1 = \displaystyle \frac{2^2-1}{3} = 1$ .

$n-1$ and $n$ : Assume the formula works for $Q_{n-1}$ and $Q_n$ .

$n+1$ :

$Q_{n+1} = Q_n + 2 Q_{n-1}$

$Q_{n+1} = \displaystyle \frac{2^{n+1} + (-1)^n}{3} + 2 \cdot \frac{2^n + (-1)^{n-1}}{3}$

$Q_{n+1} = \displaystyle \frac{2^{n+1} + (-1)^n + 2 \cdot 2^n + 2 \cdot (-1)^{n-1}}{3}$

$Q_{n+1} = \displaystyle \frac{2^{n+1} + 2^{n+1} + (-1)^n - 2 \cdot (-1)^n}{3}$

$Q_{n+1} = \displaystyle \frac{2 \cdot 2^{n+1} - (-1)^n}{3}$

$Q_{n+1} = \displaystyle \frac{2^{n+2} + (-1)^{n+1}}{3}$

That’s the formula if $n$ is replaced by $n+1$ , and so we’re done.

Let me note parenthetically that the above simplification is not all intuitive when encountered by students for the first time — even really bright students who know the laws of exponents cold and who know full well that $x + x = 2x$ and $x - 2x = -x$ . That said, I’ve found that simplifications like $2^{n+1} + 2^{n+1} = 2 \cdot 2^{n+1} = 2^{n+2}$ are usually a little intimidating to most students at first blush, though they can quickly get the hang of it.

By this point, I’m usually near the end of my 50-minute fun lecture. Since students are not responsible for replicating the contents of the fun lecture, I’ve found that most students are completely comfortable with this pace of presentation.

Then I ask my students which way they’d prefer: generating functions or mathematical induction? They usually respond induction. However, they also are able to realize that the thing that makes mathematical induction is also the challenge: they have to guess the correct formula and then use induction to verify that the formula actually works. On the other hand, with generating functions, there’s no need to guess the correct answer… you just follow the steps and see what comes out the other side.

Finally, to close the fun lecture, I tell them that the above steps can be used to find a closed-form expression for the Fibonacci sequence. (I devised the Quintanilla sequence for pedagogical purposes: since the denominator of its generating function easily factors, the subsequent steps aren’t too messy.) I won’t go through all the steps here, so I’ll leave it as a challenge for the reader to start with the generating function

$f(x) = \displaystyle \frac{1}{1-x-x^2}$ ,

factor the denominator by finding the two real roots of $1 - x - x^2 = 0$ , and then mimicking the above steps. If you want to cheat, just use the following Google search to find the answer: http://www.google.com/#q=fibonacci+%22generating+function%22

I conclude this post with some pedagogical reflections. I taught this fun lecture to about 10 different Precalculus classes, and it was a big hit each time. I think that my students were thoroughly engaged with the topic and liked seeing an unorthodox application of the various topics in Precalculus that they were learning (sequences, series, partial fractions, factoring polynomials over $\mathbb{R}$ , mathematical induction). So even though they would likely receive a fuller treatment of generating functions in a future course like Discrete Mathematics, I liked giving them this little hint of what was lying out there for them in the future.

I covered the content of this series of five posts in a 50-minute lecture. I’d usually finish the proof by induction as time expired and then would challenge them to think about how to similarly find the formula for the Fibonacci sequence. The rules of a “fun lecture” were important to pull this off — I made it clear that students would not have to do this for homework, so the pressure was off them to understand the fine details during the lecture. Instead, the idea was for them to appreciate the big picture of how topics in Precalculus can be used in future courses.

Engaging students: Dividing fractions

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

This student submission comes from my former student Dale Montgomery. His topic, from Pre-Algebra: dividing fractions.

Applications

A Short Play On Numbers

By: Dale Montgomery

You see two brothers talking in the playground.

Timmy: (little brother) Gee Jonny, it sure was a good idea to sell Joe our old Pokémon deck. Now he finally has some cards to play with and we have some money to buy some new cards.

Jonny: (older brother) Yeah, I am glad we could help him get started. He has been wanting some cards for so long. Ok, you have the money so give me half.

Timmy: Ummm… (puzzling) Jonny I don’t know how to make half of 6 dollars and fifty cents, can you help?

Jonny: Of course Timmy, I learned how to divide fractions last week… lets see. (Jonny writes on the board 6 and ½ divided by 1/2 and does the division)

Timmy: How is half more than what we started with?

Jonny: I don’t know, this is the way my teacher taught me to do it. I guess you just have to find 13 dollars to give me so I can have half.

End Scene

Teacher: So class, what did Jonny do?

I came up with this idea thinking about the student asked question regarding dividing pie in half. I feel this could be a common misconception that would be addressed if we could teach students to think about math in context, rather than just a process. Dividing fractions is not the easiest thing to conceive. This short skit could be presented in any number of formats. I like the idea of having some sort of recorded show, just because it would make the intro to class go much faster. This skit introduces a situation that is very similar to word problems that children do. Also, the content can easily be modified to fit the majority class interest. For example it could have been an old Nintendo DS game that the brothers no longer play. This puts a problem that could be very real for the students right in front of them to figure out the correct process. It could lead to good discussion and make for a good lesson on dividing fractions.

Manipulative

Fraction bars are great tools to help students visualize dividing fractions. For example, if you wanted to divide 2/3 by 1/6 you would line up two of the third bars alongside one of the sixth bar and find out how many times that fraction goes into 2 thirds. In this case it would be four. Fractions themselves are extremely difficult to visualize, and dividing by fractions seems conceptually ridiculous. It can be difficult to adjust student’s thinking to this area. A manipulative like fraction bars are a good starting point in helping kids understand just how fractions work.

Curriculum, future uses

The topic of dividing fractions has many uses in future courses. Primarily these will be in algebra 1 and 2 for most students. Having a good conceptual knowledge of fractions will help students tremendously in these courses. As an algebra student you would be required to use your knowledge of fractions on an almost daily basis. Being introduced to the concept of multiple variables and canceling them out as you divide polynomials is a very complicated process that gets even more complicated if you do not understand fractions. Laying this conceptual framework is important when you consider all that students must use these concepts for at the higher level math classes. As you consider this in the lessons don’t forget the previous concepts held here such as grouping into equal parts and counting by intervals (3,6,9).

Engaging students: Mathematical induction

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

This student submission comes from my former student Dale Montgomery. His topic, from Precalculus: mathematical induction.

Technology

https://www.khanacademy.org/math/trigonometry/seq_induction/proof_by_induction/v/proof-by-induction

Looking at Khanacademy’s video on mathematical induction, I feel like he has one of the better explanations of mathematical induction that I have heard. This lends itself well to starting class off with a video to engage, and then moving on to an explore where the students test what can or can’t be proved by induction. This quick explanation by Khan gives a good starting point, and the fact that his videos are interesting should be sufficient enough to engage the students. Another possibility is to have the students watch this at home, that way you have more time during class do work on learning how to use the principle of induction.

Application

This problem, and proof (taken from Wikipedia) has flawed logic. In it, it uses the principle of mathematical induction. This would be a good engage because it has supposedly sound logic but it says something that is obviously not true. This will engage the students by showing them something that doesn’t make sense. This will cause a imbalance in their thinking, and make them want to make sense of the situation. I would probably present it as a bell ringer or similar problem, after induction has been introduced.

All horses are the same color

The argument is proof by induction. First we establish a base case for one horse ( $n = 1$ ). We then prove that if $n$ horses have the same color, then $n+1$ horses must also have the same color.

Base case: One horse

The case with just one horse is trivial. If there is only one horse in the “group”, then clearly all horses in that group have the same color.

Inductive step

Assume that $n$ horses always are the same color. Let us consider a group consisting of $n+1$ horses.

First, exclude the last horse and look only at the first horses; all these are the same color since horses always are the same color. Likewise, exclude the first horse and look only at the last horses. These too, must also be of the same color. Therefore, the first horse in the group is of the same color as the horses in the middle, who in turn are of the same color as the last horse. Hence the first horse, middle horses, and last horse are all of the same color, and we have proven that:

If $n$ horses have the same color, then $n+1$ horses will also have the same color.

We already saw in the base case that the rule (“all horses have the same color”) was valid for $n=1$ . The inductive step showed that since the rule is valid for $n=1$ , it must also be valid for $n=2$ , which in turn implies that the rule is valid for $n=3$ and so on.

Thus in any group of horses, all horses must be the same color.

(taken from http://en.wikipedia.org/wiki/All_horses_are_the_same_color )

The explanation relies on the fact that a set of a single element cannot have 2 different sets with the same element. Because this assumption cannot be made, the case of $n=2$ falls apart and tears the argument apart.

Application

Dominoes have been talked about as a way to explain mathematical induction. The idea that if you can prove that the first one falls, and you can prove that in general if a domino falls, the one after it will fall, you can prove that the entire row of dominoes would fall. I think it would be fun to students to actually demonstrate this idea. It would even be fun to illustrate what would happen if you cannot prove that the first one falls by gluing the dominoes to whatever surface that you are using (not the table).

The idea would be to have it set up as the students walked in and ask them what would happen if you pushed over the first domino. After that test the hypothesis with one row (you should probably have multiple rows set up for this). Then introduce the concepts of base case and induction step using the dominos. Then you can ask well what if we cannot push the first domino over, does that mean we cannot show that all of the dominos will fall? After this you can start taking the concept of dominos and applying it to Mathematical induction.

Importance of the base case in a proof by induction

In Precalculus, Discrete Mathematics or Real Analysis, an arithmetic series is often used as a student’s first example of a proof by mathematical induction. Recall, from Wikipedia:

Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers. It is done in two steps. The first step, known as the base case, is to prove the given statement for the first natural number. The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number. From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers.

The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

The basis (base case): prove that the statement holds for the first natural number $n$ . Usually, $n=0$ or $n=1$ .

The inductive step: prove that, if the statement holds for some natural number $n$ , then the statement holds for $n+1$ .

The hypothesis in the inductive step that the statement holds for some $n$ is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for $n+1$ .

As an inference rule, mathematical induction can be justified as follows. Having proven the base case and the inductive step, then any value can be obtained by performing the inductive step repeatedly. It may be helpful to think of the domino effect. Consider a half line of dominoes each standing on end, and extending infinitely to the right. Suppose that:

The first domino falls right.

If a (fixed but arbitrary) domino falls right, then its next neighbor also falls right.

With these assumptions one can conclude (using mathematical induction) that all of the dominoes will fall right.

Mathematical induction… works because $n$ is used to represent an arbitrary natural number. Then, using the inductive hypothesis, i.e. that $P(n)$ is true, show $P(k+1)$ is also true. This allows us to “carry” the fact that $P(0)$ is true to the fact that $P(1)$ is also true, and carry $P(1)$ to $P(2)$ , etc., thus proving $P(n)$ holds for every natural number $n$ .

When students first encounter mathematical induction (in either Precalculus, Discrete Mathematics, or Real Analysis), the theorems that students are asked to prove usually fall into four categories:

Calculating a series (examples below).
Statements concerning divisibility (for example, proving that $4$ is always a factor of $5^n-1$ ).
Finding a closed-form expression for a recursively defined sequence (for example, if $a_1 = 4$ and $a_n = 3a_{n-1}$ if $n \ge 2$ , proving that $a_n = 4 \times 3^{n-1}$ )
Statements concerning inequality (for example, proving that $n! > 4^n$ if $n \ge 9$ )

Here’s a common first (or maybe second) example of mathematical induction applied to an arithmetic series.

Theorem. $1^2 + 2^2 + \dots + (n-1)^2 + n^2 = \displaystyle \frac{n(n+1)(2n+1)}{6}$

Proof. Induction on $n$ .

$n = 1$ : The left-hand is simply $1$ , while the right-hand side is $\displaystyle \frac{(1)(2)(3)}{6}$ , which is also equal to $1$ . So the base case works.

$n$ : Assume that the statement holds true for the integer $n$ .

$n+1$ . If I replace $n$ by $n+1$ in the statement of the theorem, then the right-hand side becomes

$\displaystyle \frac{(n+1)[(n+1)+1][2(n+1)+1]}{6} = \displaystyle \frac{(n+1)(n+2)(2n+3)}{6}$

I find it helpful to describe this to students as my target. In other words, as I manipulate the left-hand side, my ultimate goal is to end up with this target. Once I have done that, then I have completed the proof.

If I replace $n$ by $n+1$ in the statement of the theorem, then the left-hand side will now end on $n+1$ instead of $n$ :

$1^2+ 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2$

Notice that we’ve seen almost all of this before, except for the extra term $(n+1)^2$ . So we will substitute using the induction hypothesis, carrying the extra $(n+1)^2$ along for the ride.

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{n(n+1)(2n+1)}{6} + (n+1)^2$

Now our task is, by hook or by crook, using whatever algebraic tricks we can think of to convert this last expression into the target. Most students are completely comfortable doing this, although they typically multiply out the term $n(n+1)(2n+1)$ unnecessarily. Indeed, many early proofs by induction are simplified by factoring out terms whenever possible — in the example below, $(n+1)$ is factored on the third step — as opposed to multiplying them out. In my experience, proofs by induction often serve as a stringent test of students’ algebra skills as opposed to their skills in abstract reasoning.

In any event, here’s the end of the proof:

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{n(n+1)(2n+1)}{6} + (n+1)^2$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{n(n+1)(2n+1) + 6(n+1)^2}{6}$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{(n+1)[n(2n+1) + 6(n + 1)]}{6}$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{(n+1)(2n^2 + n + 6n + 6)}{6}$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{(n+1)(2n^2 + 7n + 6)}{6}$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{(n+1)(n+2)(2n+3)}{6}$

A fair amount of algebra was needed to prove the $n+1$ case. However, the first step — the base case — was especially easy. Indeed, in most proofs by induction seen by students, the base case is often quite trivial… to the point that students often wonder why the base case is needed in the first place.

I first saw this next example in Calculus, by Tom M. Apostol. This next fallacious example illustrates what can happen if the base case is ignored. The statement of this “theorem” doesn’t match the formula for an arithmetic series, and so clearly something is wrong with the following “proof.”

“Theorem.” $1 + 2 + \dots + (n-1) + n = \displaystyle \frac{(2n+1)^2}{8}$

“Proof.” Induction on $n$ .

$n = 1$ : Let’s just ignore the base case, it’s unimportant.

$n$ : Assume that the statement holds true for the integer $n$ .

$n+1$ . If I replace $n$ by $n+1$ in the statement of the theorem, then the right-hand side — my target — becomes

$\displaystyle \frac{[2(n+1)+1]^2}{8} = \displaystyle \frac{(2n+3)^2}{8}$

On the left-hand side, we use the induction hypothesis:

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(2n+1)^2}{8} + (n+1)$

Now our task is, by hook or by crook, using whatever algebraic tricks we can think of to convert this last expression into the target.

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(2n+1)^2}{8} + (n+1)$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(2n+1)^2 + 8(n+1)}{8}$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{4n^2+4n+1+8n+8}{8}$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{4n^2+12n+9}{8}$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(2n+3)^2}{8}$

So that’s the end of the “proof.”

Clearly, something went wrong with the above proof. What went wrong, obviously, is that we didn’t check the base case. If $n=1$ , then the left-hand side is $1$ . However, the right-hand side is $\displaystyle \frac{[(2)(1) + 1]^2}{8} = \displaystyle \frac{9}{8}$ . So the base case is false.

So what happened?

We correctly showed that, if the case $n$ is true, then the case $n+1$ is also true. The catch, of course, is that the case $n$ is never true. Using the domino analogy, we showed that if a domino falls, then the next domino will fall. But the first domino never falls.

All this to say… yes, it’s important to check that the base case actually works.