High School Students Finding New Proofs of Old Theorems (Part 1): Dividing a line segment with straightedge and compass

This is one of my all-time favorite stories to share with students: how a couple of ninth graders in 1995 played with Geometer’s Sketchpad and stumbled upon a brand-new way of using only a straightedge and compass to divide a line segment into any number of equal-sized parts. This article was published in 1997 and made quite a media sensation at the time.

1997_litchfieldd._euclidfibonaccisketchpad Download

Solving Problems Submitted to MAA Journals (Part 3)

The following problem appeared in Volume 53, Issue 4 (2022) of The College Mathematics Journal.

Define, for every non-negative integer $n$ , the $n$ th Catalan number by

$C_n := \displaystyle \frac{1}{n+1} {2n \choose n}$ .

Consider the sequence of complex polynomials in $z$ defined by $z_k := z_{k-1}^2 + z$ for every non-negative integer $k$ , where $z_0 := z$ . It is clear that $z_k$ has degree $2^k$ and thus has the representation

$z_k =\displaystyle \sum_{n=1}^{2^k} M_{n,k} z^n$ ,

where each $M_{n,k}$ is a positive integer. Prove that $M_{n,k} = C_{n-1}$ for $1 \le n \le k+1$ .

This problem appeared in the same issue as the probability problem considered in the previous two posts. Looking back, I think that the confidence that I gained by solving that problem gave me the persistence to solve this problem as well.

My first thought when reading this problem was something like “This involves sums, polynomials, and binomial coefficients. And since the sequence is recursively defined, it’s probably going to involve a proof by mathematical induction. I can do this.”

My second thought was to use Mathematica to develop my own intuition and to confirm that the claimed pattern actually worked for the first few values of $z_k$ .

As claimed in the statement of the problem, each $z_k$ is a polynomial of degree $2^k$ without a nontrivial constant term. Also, for each $z_k$ , the term of degree $n$ , for $1 \le n \le k+1$ , has a coefficient that is independent of $k$ which equal to $C_{n-1}$ . For example, for $z_4$ , the coefficient of $z^5$ (in orange above) is equal to

$C_4 = \displaystyle \frac{1}{5} {8 \choose 4} = \frac{8!}{4! 4! \cdot 5} = \frac{40320}{2880} = 14$ ,

and the problem claims that the coefficient of $z^5$ will remain 14 for $z_5, z_6, z_7, \dots$

Confident that the pattern actually worked, all that remained was pushing through the proof by induction.

We proceed by induction on $k$ . The statement clearly holds for $k=1$ :

$z_1 = z_0^2 + z = z + z^2 = C_0 z + C_1 z^2$ .

Although not necessary, I’ll add for good measure that

$z_2 = z_1^2 + z = (z^2+z)^2 + z = z + z^2 + 2z^3 + z^4 = C_0 z + C_1 z^2 + C_2 z^3 + z^4$

and

$z_3 = z^2 + z = (z^4+2z^3+z^2+z)^2 + z$

$= z + z^2 + 2z^3 + 5z^4 + 6z^5 + 6z^6 + 4z^7 + z^8$

$= C_0 z + C_1 z^2 + C_2 z^3 + C_3 z^4 + 6z^5 + 6z^6 + 4z^7 + z^8.$

This next calculation illustrates what’s coming later. In the previous calculation, the coefficient of $z^4$ is found by multiplying out

$(z^4+2z^3+z^2+z)(z^4+2z^3+z^2+z)$ .

This is accomplished by examining all pairs, one from the left product and one from the right product, so that the exponent works out to be $z^4$ . In this case, it’s

$(2z^3)(z) + (z^2)(z^2) + (z)(2z^3) = 5z^4$ .

For the inductive step, we assume that, for some $k \ge 1$ , $M_{n,k} = C_{n-1}$ for all $1 \le n \le k+1$ , and we define

$z_{k+1} = z + \left( M_{1,k} z + M_{2,k} z^2 + M_{3,k} z^3 + \dots + M_{2^k,k} z^{2^k} \right)^2$

Our goal is to show that $M_{n,k+1} = C_{n-1}$ for $n = 1, 2, \dots, k+2$ .

For $n=1$ , the coefficient $M_{1,k+1}$ of $z$ in $z_{k+1}$ is clearly 1, or $C_0$ .

For $2 \le n \le k+2$ , the coefficient $M_{n,k+1}$ of $z^n$ in $z_{k+1}$ can be found by expanding the above square. Every product of the form $M_{j,k} z^j \cdot M_{n-j,k} z^{n-j}$ will contribute to the term $M_{n,k+1} z^n$ . Since $n \le k+2 \le 2^k+1$ (since $k \ge 1$ ), the values of $j$ that will contribute to this term will be $j = 1, 2, \dots, n-1$ . (Ordinarily, the $z^0$ and $z^n$ terms would also contribute; however, there is no $z^0$ term in the expression being squared). Therefore, after using the induction hypothesis and reindexing, we find

$M_{n,k+1} = \displaystyle \sum_{j=1}^{n-1} M_{j,k} M_{n-j,k}$

$= \displaystyle\sum_{j=1}^{n-1} C_{j-1} C_{n-j-1}$

$= \displaystyle\sum_{j=0}^{n-2} C_j C_{n-2-j}$

$= C_{n-1}$ .

The last step used a recursive relationship for the Catalan numbers that I vaguely recalled but absolutely had to look up to complete the proof.

My Favorite One-Liners: Part 98

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

I’ll use today’s quip just after introducing the methodology of mathematical induction to my students:

Induction is so easy that even the army uses it.

My Favorite One-Liners: Part 43

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them. q Q

Years ago, my first class of students decided to call me “Dr. Q” instead of “Dr. Quintanilla,” and the name has stuck ever since. And I’ll occasionally use this to my advantage when choosing names of variables. For example, here’s a typical proof by induction involving divisibility.

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.

At this point in the calculation, I ask how I can write this statement as an equation. Eventually, somebody will volunteer that if $5^n-1$ is a multiple of 4, then $5^n-1$ is equal to 4 times something. At which point, I’ll volunteer:

Yes, so let’s name that something with a variable. Naturally, we should choose something important, something regal, something majestic… so let’s choose the letter $q$ . (Groans and laughter.) It’s good to be the king.

So the proof continues:

$n$ : Assume that $5^n - 1 = 4q$ , where $q$ is an integer.

$n+1$ . We wish to show that $5^{n+1} - 1$ is also a multiple of 4.

At this point, I’ll ask my class how we should write this. Naturally, I give them no choice in the matter:

We wish to show that $5^{n+1} - 1 = 4Q$ , where $Q$ is some (possibly different) integer.

Then we continue the proof:

$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

On the flip side of braggadocio, the formula for the binomial distribution is

$P(X = k) = \displaystyle {n \choose k} p^k q^{n-k}$ ,

where $X$ is the number of successes in $n$ independent and identically distributed trials, where $p$ represents the probability of success on any one trial, and (to my shame) $q$ is the probability of failure.

My Favorite One-Liners: Part 28

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them. Today’s quip is one that I’ll use when simple techniques get used in a complicated way.

Consider the solution of the linear recurrence relation

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

where $F_0 = 1$ and $F_1 = 1$ . With no modesty, I call this one the Quintanilla sequence when I teach my students — the forgotten little brother of the Fibonacci sequence.

To find the solution of this linear recurrence relation, the standard technique — which is a pretty long procedure — is to first solve the characteristic equation, from $Q_n - Q_{n-1} - 2 Q_{n-2} = 0$ , we obtain the characteristic equation

$r^2 - r - 2 = 0$

This can be solved by any standard technique at a student’s disposal. If necessary, the quadratic equation can be used. However, for this one, the left-hand side simply factors:

$(r-2)(r+1) = 0$

$r=2 \qquad \hbox{or} \qquad r = -1$

(Indeed, I “developed” the Quintanilla equation on purpose, for pedagogical reasons, because its characteristic equation has two fairly simple roots — unlike the characteristic equation for the Fibonacci sequence.)

From these two roots, we can write down the general solution for the linear recurrence relation:

$Q_n = \alpha_1 \times 2^n + \alpha_2 \times (-1)^n$ ,

where $\alpha_1$ and $\alpha_2$ are constants to be determined. To find these constants, we plug in $n =0$ :

$Q_0 = \alpha_1 \times 2^0 + \alpha_2 \times (-1)^0$ .

To find these constants, we plug in $n =0$ :

$Q_0 = \alpha_1 \times 2^0 + \alpha_2 \times (-1)^0$ .

We then plug in $n =1$ :

$Q_1 = \alpha_1 \times 2^1 + \alpha_2 \times (-1)^1$ .

Using the initial conditions gives

$1 = \alpha_1 + \alpha_2$

$1 = 2 \alpha_1 - \alpha_2$

This is a system of two equations in two unknowns, which can then be solved using any standard technique at the student’s disposal. Students should quickly find that $\alpha_1 = 2/3$ and $\alpha_2 = 1/3$ , so that

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

which is the final answer.

Although this is a long procedure, the key steps are actually first taught in Algebra I: solving a quadratic equation and solving a system of two linear equations in two unknowns. So here’s my one-liner to describe this procedure:

This is just an algebra problem on steroids.

Yes, it’s only high school algebra, but used in a creative way that isn’t ordinarily taught when students first learn algebra.

I’ll use this “on steroids” line in any class when a simple technique is used in an unusual — and usually laborious — way to solve a new problem at the post-secondary level.

My Favorite One Liners: Part 2

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

When doing a large computation, I’ll often leave plenty of blank space on the board to fill it later. For example, when proving by mathematical induction that

$1 + 3 + 5 + \dots + (2n-1) = n^2$ ,

the inductive step looks something like

$1 + 3 + 5 \dots + (2k-1) + (2[k+1]-1) =$

$~$

$= (k+1)^2$

So I explained that, to complete the proof by induction, all we had to do was convert the top line into the bottom line.

As my class swallowed hard as they thought about how to perform this task, I told them, “Yes, this looks really intimidating. Indeed, to quote the great philosopher, ‘You might think that I’m insane. But I’ve got a blank space, baby… so let’s write what remains.’ “

And, just in case you’ve been buried under a rock, here’s the source material for the one-liner (which, at the time of this writing, is the fifth-most watched video on YouTube):

What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 9

When teaching students mathematical induction, the following series (well, at least the first two or three) are used as typical examples:

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

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

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

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

What I didn’t know (Gamma, page 81) is that Johann Faulhaber published the following cute result in 1631 (see also Wikipedia): If $k$ is odd, then

$1^k + 2^k + 3^k + \dots + n^k = f_k(n(n+1))$ ,

where $f_k$ is a polynomial. For example, to match the above examples, $f_1(x) = x/2$ and $f_3(x) = x^2/4$ . Furthermore, if $k$ is even, then

$1^k + 2^k + 3^k + \dots + n^k = (2n+1) f_k(n(n+1))$ ,

where again $f_k$ is a polynomial. For example, to match the above examples, $f_2(x) = x/6$ and $f_3(x) = x(3x-1)/30$ .

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$ , the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

Mathematical induction and blank space

I tried out a one-liner in class that I’d been itching to try all summer.

I was introducing my students to proofs by mathematical induction; my example was showing that

$1 + 3 + 5 + \dots + (2n-1) = n^2$ .

After describing the principle of mathematical induction, I wrote out the $n = 1$ step and the assumption for $n = k$ :

$n=1$ : $1=1^2$ , so this checks.

$n =k$ : Assume that $1 + 3 + 5 + \dots + (2k-1) = k^2$ .

Then, for the inductive step, I had my students tell me what the left- and right-hand side would be if I substituted $k+1$ in place of $n$ . I wrote the answer for the left-hand side at the top of the board, the answer for the right-hand side at the bottom of the board, and left plenty of blank space in between the two (which I would fill in shortly):

$n = k+1$ :

$1 + 3 + 5 \dots + (2k-1) + (2[k+1]-1) =$

$~$

$= (k+1)^2$

So I explained that, to complete the proof by induction, all we had to do was convert the top line into the bottom line.

The one-liner provoked the desired response from my students… and after the laughter died down, we then worked through the end of the proof.

And, just in case you’ve been buried under a rock for the past few months, here’s the source material for the one-liner (which, at the time of this writing, is the second-most watched video on YouTube):

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.