PROOF

This discussion addresses several different aspects of proof and includes many links to additional readings. You may want to jump to the activities, try some out, and then double back to the readings once you have had a chance to reflect on how you approach proofs. You can use the table of contents below to navigate around this chapter:

What Is a Proof?

Why Do We Prove?

What Do We Prove?

When Should Students Prove?

How Do We Prove?

When Is a Proof Finished?

Writing Proofs

Evaluating Proofs

Class activity

Practice Proof Activities

A setting for whole class practice

Other whole class problems and resources

Proof without words

Twenty practice problems (with solutions)

Bibliography

WHAT IS A PROOF?

In everyday life, we frequently reach conclusions based on anecdotal evidence. This habit also guides our work in the more abstract realm of mathematics, but mathematics requires us to adopt a greater level of skepticism. Examples—no matter how many—are never a proof of a claim that covers an infinite number of instances.

A proof is a logical argument that establishes the truth of a statement. The argument derives its conclusions from the premises of the statement, other theorems, definitions, and, ultimately, the postulates of the mathematical system in which the claim is based. By logical, we mean that each step in the argument is justified by earlier steps. That is, that all of the premises of each deduction are already established or given. In practice, proofs may involve diagrams that clarify, words that narrate and explain, symbolic statements, or even a computer program (as was the case for the Four Color Theorem (MacTutor)). The level of detail in a proof varies with the author and the audience. Many proofs leave out calculations or explanations that are considered obvious, manageable for the reader to supply, or which are cut to save space or to make the main thread of a proof more readable. In other words, often the overarching objective is the presentation of a convincing narrative.

Postulates are a necessary part of mathematics. We cannot prove any statement if we do not have a starting point. Since we base each claim on other claims, we need a property, stated as a postulate, that we agree to leave unproven. The absence of such starting points would force us into an endless circle of justifications. Similarly, we need to accept certain terms (e.g., "point" or "set") as undefined in order to avoid circularity (see Writing Definitions). In general, however, proofs use justifications many steps removed from the postulates.

Before the nineteenth century, postulates (or axioms) were accepted as true but regarded as self-evidently so. Mathematicians tried to choose statements that seemed irrefutably true—an obvious consequence of our physical world or number system. Now, when mathematicians create new axiomatic systems, they are more concerned that their choices be interesting (in terms of the mathematics to which they lead), logically independent (not redundant or derivable from one another), and internally consistent (theorems which can be proven from the postulates do not contradict each other). (Download Axiomatic Systems (Lee) and see sections 6.1, 8.1, and 8.4 in book 3b of Math Connections (Berlinghoff) for further explanations, activities, and problem sets on axiomatic systems, consistency, and independence). For example, non-Euclidean geometries have been shown to be as consistent as their Euclidean cousin. The equivalence between these systems does not mean that they are free of contradictions, only that each is as dependable as the other. This modern approach to axiomatic systems means that we consider statements to be true only in the context of a particular set of postulates.

WHY DO WE PROVE?

To Establish a Fact with Certainty

There are many possible motives for trying to prove a conjecture. The most basic one is to find out if what one thinks is true is actually true. Students are used to us asking them to prove claims that we already know to be true. When students investigate their own research questions, their efforts do not come with a similar guarantee. Their conjecture may not be true or the methods needed may not be accessible. However, the only way that they can be sure that their conjecture is valid, that they have in fact solved a problem, is to come up with a proof.

Students’ confidence in a fact comes from many sources. At times, they appeal to an authoritative source as evidence for a claim: "it was in the text" or "Ms. Noether told us this last year." It has been my experience that such justifications carry little practical persuasive value. For example, a class discussed the irrationality of and proofs of that fact, yet an essay assignment on a proposal to obtain the complete decimal expansion of still generated student comments such as, "if eventually turns out not to be irrational then that project would be interesting." Thus, an authoritative claim of proof is only good until some other authority shows otherwise. Mathematical truths do tend to stand the test of time. When students create a proof themselves, they are less likely to think of the result as ephemeral. A proof convinces the prover herself more effectively than it might if generated by someone else.

To Gain Understanding

"I would be grateful if anyone who has understood this demonstration would explain it to me."

– Fields Medal winner Pierre Deligne, regarding a theorem that he proved using methods that did not provide insight into the question.

There are proofs that simply prove and those that also illuminate. As in the case of the Deligne quote above, certain proofs may leave one unclear about why a result is true but still confident that it is. Proofs with some explanatory value tend to be more satisfying and appealing. Beyond our interest in understanding a given problem, our work on a proof may produce techniques and understandings that we can apply to broader questions. Even if a proof of a theorem already exists, an alternative proof may reveal new relationships between mathematical ideas. Thus, proof is not just a source of validation, but an essential research technique in mathematics.

If our primary consideration for attempting a proof is to gain insight, we may choose methods and types of representations that are more likely to support that objective. For example, the theorem that the midpoints of any quadrilateral are the vertices of a parallelogram can be proven algebraically using coordinates or synthetically (figure 1).

Figure 1. The diagrams for coordinate and synthetic proofs

A synthetic proof rests on the fact that the segment connecting the midpoints of two sides of a triangle, the midline, is parallel to the third side. In quadrilateral ABCD (right side of figure 1), the midlines of triangles ABD and CBD are both parallel to the quadrilateral diagonal BD and, therefore, to each other. It is clear that if point C were to move, the midline for triangle BCD would remain parallel to both BD and the midline of triangle ABD. To complete the proof, one would consider the midlines of triangle ADC and triangle ABC as well. The coordinate proof uses the coordinates of the midpoints to show that the slopes of opposite midlines are equal.

For many people, the synthetic proof is more revealing about why any asymmetries of the original quadrilateral do not alter the properties of the inner parallelogram. It also illustrates how a proof can be a research tool by answering other questions, such as "when will the inner quadrilateral be a rhombus?" Because midlines are one half the length of the parallel side, the inner parallelogram will have equal sides only when the diagonals of the original quadrilateral are congruent.

Sometimes our inability to develop a proof is revealing and leads us to reconsider our examples or intuitions. After countless attempts to prove that Euclid’s fifth postulate (the parallel postulate) was dependent on the other four, mathematicians in the nineteenth century finally asked what the consequences would be if the postulate were independent. The doubts that arose from the failure to obtain a proof led to the creation of non-Euclidean geometries.

To Communicate an Ideas to Others

Often, mathematicians (of both the student and adult variety) have a strong conviction that a conjecture is true. Their belief may stem from an informal explanation or some convincing cases. They do not harbor any internal doubt, but there is a broader audience that retains some skepticism. A proof allows the mathematician to convince others of the correctness of their idea. A Making Mathematics teacher, in the midst of doing research with colleagues, shared his feelings about proof:

Just so I can get it off of my chest, I hate doing proofs with a passion. It’s the part of mathematics that I grew to hate when I was an undergraduate, and it’s what so many of my former students come back and tell me turned them off to continuing on as a math major. I remember having a professor who held us responsible for every proof he did in class. We’d probably have a dozen or more to know for each exam, in addition to understanding the material itself. I can remember just memorizing the steps, because the approaches were so bizarre that no "normal person" would ever think of them in a million years (yes, I know I'm stereotyping).

This teacher’s frustrations with proofs involved having to memorize arguments that were neither revealing (and therefore, not entirely convincing) nor sufficiently transparent about the process by which they were created. Yet, this same teacher, on encountering collegial doubts about his conjecture concerning Pascal’s triangle wrote, "Well, I decided to try and convince you all that the percentage of odds does in fact approach zero as the triangle grows by proving it." His efforts over several days produced a compelling proof. His conflicting attitudes and actions highlight the distinction between proofs as exercises and proofs as tools for communication and validation. A genuine audience can make an odious task palatable.

For the Challenge

Difficult tasks can be enjoyable. Many mathematical problems are not of profound significance, yet their resolution provides the person who solves them with considerable gratification. Such success can provide a boost in self-esteem and mathematical confidence. The process of surmounting hurdles to a proof can have all of the thrill of a good mystery. Students (and adults) are justifiably excited when they solve a problem unlike any they have previously encountered and which no one else may have ever unraveled.

To Create Something Beautiful

The more students engage in mathematics research, the more they develop their own aesthetic for mathematical problems and methods. The development of a proof that possesses elegance, surprises us, or provides new insight is a creative act. It is rewarding to work hard to make a discovery or develop a proof that is appealing. The mathematician Paul Erdös spoke of proofs that were "straight from the Book"—the Book being God’s collection of all the perfect proofs for every theorem. Although Erdös did not actually believe in God, he did believe that there were beautiful truths waiting to be uncovered (Hoffman).

To Construct a Larger Mathematical Theory

We rarely consider mathematical ideas in a vacuum. Our desire to advance a broader mathematical problem is often a source of motivation when we attempt a proof. For example, a number of mathematicians spent many years attempting to characterize a class of objects known as simple groups (Horgan). Their cumulative efforts resulted in thousands of pages of proofs that together accomplished the task. Many of these proofs, significant in their own right, were of even greater value because of their contribution to the larger understanding that the mathematics community sought.

For a further discussion of the role of proof in school curricula, see Do We Need Proof in School Mathematics? (Schoenfeld, 1994).

WHAT DO WE PROVE?

We can prove many different types of claims.

• We can show that an object or a set of objects possesses some particular property. For example, we can prove that all isosceles trapezoids have a circumcircle or that all rational numbers have finite or repeating decimal representations.
• We can prove that a particular algorithm will construct objects with a desired property. For example, we can prove that a geometric construction does produce a specific shape or that the formula (n² – m², 2mn, n² + m²) will always produce Pythagorean triples for counting numbers m and n with n > m (see PythagoreanTriples, Bogomolny).
• More surprisingly, we can also prove that objects with certain properties exist without having to produce the objects themselves. Euclid’s proof of the infinitude of the prime numbers is one such existence proof (see Infinitude of Primes, Bogomolny). Euclid showed that, given any finite set of primes, there must always be another prime not within the set, but his method does not produce that next number. Likewise, we can count the number of trains of length n that can be made from cars of different lengths without showing how to generate the arrangements of cars themselves (see the teaching notes for the trains project for examples of both constructive and non-constructive proofs of the number of trains n units long).
• When we cannot determine the precise solution to a problem, we may seek to estimate it or prove that there are boundaries to the answer. If a function cannot be determined explicitly, we can try to approximate its behavior asymptotically. The project Set considers the maximum number of three-card Sets possible in a carefully constructed collection of n cards (see the teaching notes). We do not know the exact maximum for n even as small as 12, but we have established upper and lower limits. The distribution of primes is a central question in number theory. The function P(n) that gives the number of primes less than or equal to n can be found by identifying all primes up to n. Beyond the bounds of calculation, it can still be accurately estimated using the prime number theorem (see Prime Theorem of the Century, Peterson).
• We can show that two different problems or systems are related to each other. For example, in 1868, Eugenio Beltrami demonstrated that Lobachevskian geometry could be modeled within Euclidean geometry and that the two were, therefore, equivalently consistent or inconsistent (see Non-Euclidean Geometries, Models, Bogomolny).
• We can prove the impossibility of some type of claim. Some of the most important of all such proofs are Gödel’s Incompleteness Theorems. These theorems revealed that any axiomatic system that includes the properties of arithmetic would have statements that cannot be proven within the system. That is, it is impossible to create a complete axiomatic system that is complex enough to support most mathematical work (see Gödel’s Theorems (PRIME), The Limits of Mathematics (Peterson) and The Berry Paradox (Chaitin)).

WHEN SHOULD STUDENTS PROVE?

In general, students should attempt a proof in response to one of the motivations listed in the Why Do We Prove? section. If students only attempt proofs as exercises, they come to see proof as an after-the-fact verification of what someone else already knows—it becomes disconnected from the process of acquiring new knowledge. However, students derive considerable satisfaction from proving a claim that has arisen from their own investigations.

If students in a class disagree about a conjecture, then that is a good time for the individuals who support it to look for a proof in order to convince the doubters. If a student seems particularly taken with a problem and starts to feel some sense of ownership for the idea, then she should attempt a proof in response to her own mathematical tastes. If two student claims have a connection, the students may want to prove the one that is a prerequisite for proving the other.

A focus on formal proof should grow gradually. When we emphasize formal proof too soon and too often, before students have developed a rich repertoire of proof techniques and understanding, their frustration with, and subsequent dislike of, the challenge can become an obstacle to further progress. It is always appropriate to ask students what led them to their conjectures and why they think they are true. We begin by asking for reasons, not formal proofs, and establish the expectation that explanations should be possible and are important. Note that we ask "why" regardless of the correctness of a claim and not just for false propositions. As we highlight that they always should be interested in why an idea is true, students begin to develop the habit of asking "why?" themselves.

A good time to ask a student to write out a proof is when you think that she has already grasped the connections within a problem that are essential to the development of a more formal argument. This timing will not only lead to an appreciation for how proofs can arise organically during research, it will also lead to some confidence regarding the creation of proofs.

It is not necessary for students to prove all of their claims just for the sake of thoroughness. Published articles often prove the hard parts and leave the easier steps "for the reader." In contrast, a student should begin by trying to prove her simpler assertions (although it may be difficult to figure out how hard a problem will be in advance). When students have conjectures, label them with the students’ names and post them in the class as a list of open problems. Then, as students grow in the rigor and complexity of their proofs, they can return to questions that have become accessible.

When a student does create a proof, have her describe it to a peer, give an oral presentation to the class, or write up her thinking and hand it out for peer review. The students should come to see themselves as each other's editorial board, as a group of collaborating mathematicians. They should not be satisfied if their classmates do not understand their argument. It is a long struggle getting to the point where we can write intelligible yet efficient mathematics. One of my students once presented proofs of a theorem four times before the class gave him the "official Q.E.D". Each of the first three presentations generated questions that helped him to refine his thinking, his definitions, and his use of symbols.

HOW DO WE PROVE?

General Approaches

Learning to prove conjectures is a lifelong process, but there are some basic considerations and methods that students should focus on as they begin to develop rigorous arguments. The first concern is that they be clear about what they are trying to prove—that they unambiguously identify the premises and the conclusions of their claim (see Conditional Statements in Conjectures).

The next goal should be to try to understand some of the connections that explain why the conjecture might be true. As we study examples or manipulate symbolic representations, we gain understanding that may lead to a proof. Because understanding and proof often evolve together, if a student wants to prove a conjecture that a classmate or teacher has presented, she should consider undertaking an investigation that will help her recreate the discovery of the result. This process may provide insight into how a proof might be produced. (See Schoenfeld (1992) for more discussion of problem solving and proof.)

Often, a proof involves a large number of steps that, in our thinking about the problem, we organize into a smaller number of sequences of related steps (similar to when computer programmers turn a number of commands into a single procedure). This "chunking" of many steps into one line of reasoning makes it possible to grasp the logic of a complicated proof. It also helps us to create an outline of a potential proof before we have managed to fill in all of the needed connections (see Proof Pending a Lemma below).

When we create a proof, we seek to build a bridge between our conjecture’s premise and its conclusion. The information in the premise will have a number of possible consequences that we can use. Similarly, we try to identify the many conditions that would suffice to prove our conclusion. For example, if we know that a number is prime, there are numerous properties of prime numbers that we might bring into play. If we seek to show that two segments are congruent, we might first show that they are corresponding sides of congruent figures, that they are both congruent to some third segment, or that it is impossible for one to be either shorter or longer than the other. Once we have considered the possibilities that stem from our premises and lead to our conclusions, we have shortened the length of our proof from "if premise, then conclusion" to "if consequence-of-premise, then conditions-leading-to-conclusion" (figure 2). A main task comes in trying to determine if any of these new statements (one for each combination of consequence and condition) is likely to be easier to prove than the original.

Figure 2. Searching for a path to a proof

Some conjecture’s conclusions involve more than one claim. Recognizing all of these requirements can be a challenge. For example, to show that the formula (n² – m², 2mn, n² + m²) is a complete solution to the problem of identifying Pythagorean triples, we need to show both that it always generates such triples and that no triples are missed by the formula. Cases such as this, in which we need to demonstrate both a claim and its converse, are common.

Sometimes, two approaches to proving a result will differ in both their method and what they teach us. A student working on the Amida-kuji project defined a minimal configuration of horizontal rungs as one that results in a particular rearrangement of the numbers using the fewest rungs possible. He then conjectured that the number of distinct minimal configurations would always be greatest for the reversal of n items (1 2 3 … n goes to n … 3 2 1) than for any other permutation of the n values. Does this student need to find and prove a formula for the number of minimal configurations for each permutation? Can he somehow compare the number of minimal configurations without actually counting them explicitly and show that one set is larger? These two approaches might both prove his claim, but they require distinctly different findings along the way.

Just as we make decisions about the sequencing of ideas that we use to construct a proof, so, too, do we choose from among an array of different technical tools. In the quadrilateral proof above, we represented the same setting using coordinates as well as synthetically. We transform our mathematical ideas into diagrams, numeric examples, symbolic statements, and words. Within those broad categories, there are numerous ways of representing information and relationships and each representation offers the possibility of new understandings.

We may further our understanding of a problem by looking at a simpler version of it. We can apply this same approach to proof: prove a special case or subset of cases before taking on the entire problem. For example, a student working on the Raw Recruits project first proved theorems about the cases with one or two misaligned recruits and then worked up to the general solution. Choosing the right simplification of a problem is important. Had the student focused on a fixed number of total recruits rather than of misaligned ones, she might not have been as successful finding patterns.

Proof methods

The list of proof techniques is endless. Providing students with a repertoire of a few powerful, general methods can give them the tools that they need to get started proving their conjectures. These first techniques also whet students’ appetites to learn more. Each student’s own research and reading of mathematics articles (see Reading Technical Literature in Getting Information) will provide additional models to consider when constructing a proof. When students begin work within a new mathematical domain, they will need to learn about the tools (representations, techniques, powerful theorems) common to the problems that they are studying.

It is not possible to give ironclad rules for when a given approach to proof will prove fruitful. Therefore, in addition to providing guidance ("It might be worthwhile holding one of your variables constant"), our job mentoring students engaged in proof is to ask questions that will help them reflect on their thinking. Is planning a part of their process (are they considering alternative strategies or just plowing ahead with the first approach that occurs to them)? Are they connecting the steps that they are exploring with the goal that they are trying to reach (can they explain how their current course of action might produce a useful result)? Are they periodically revisiting the terms of their conjecture to see that they have not drifted off course in their thinking? See Getting Stuck, Getting Unstuck—Coaching and Questioning for further questions.

The most basic approach that students can use to develop understanding and then a proof is to study specific cases and seek to generalize them. For example, a student was exploring recursive functions of the form . She wanted to find an explicit formula for f and began by looking at with . Her first values:

revealed some patterns, but no breakthrough. She then took an algebraic perspective on the problem by looking at the form and not the value of the results. She decided to keep her examples general by not doing the arithmetic at each step:

This form revealed an explicit formula, , which pointed the way to a general rule for all a, b, and . This example demonstrates why it is sometimes advantageous not to simplify an expression.

Algebra is a familiar, all-purpose tool that we should encourage students to use more often. Many students primarily think of variables as specific unknowns and not as placeholders for an infinite number of examples (see the practice proofs and their solutions for examples of algebraic expressions used in this manner).

For descriptions of, and exercises using, some of the most common and powerful proof methods, see the Mathematics Tools on proof:

• proof by induction
• proof by contradiction
• the pigeonhole principle
• parity in proof
• invariants

Examples as Disproof and Proof

An example cannot prove an affirmative statement about an infinite class of objects. However, a single example, called a counterexample, is sufficient to disprove a conjecture and prove the alternative possibility. For example, we know of many even perfect numbers (Weisstein). The discovery of a single odd perfect number would be an important proof that such numbers, conjectured not to exist, are possible.

Proof By Exhaustion

When a conjecture involves a finite set of objects, we can prove the conjecture true by showing that it is true for every one of those objects. This exhaustive analysis is sometimes the only known means for answering a question. It may not be elegant, but it can get the job done if the number of instances to test is not overwhelmingly large. The mathematicians who proved the Four Color Theorem (MacTutor) broke the problem into 1476 cases and then programmed a computer to verify each one. Such proofs are not entirely satisfying because they are less likely than a proof that covers all cases simultaneously to have explanatory value.

We often break a problem down into categories of instances or cases and not all the way down to individual instances. For example, a theorem about triangles may require separate analyses for acute, right, and obtuse triangles. One challenge when proving via a case-by-case analysis is to have a rigorous means of showing that you have identified all of the different possible cases.

Proof Pending a Lemma

One of the more exciting experiences in mathematics is the recognition that two ideas are connected and that the truth of one is dependent on the truth of the other. Often a student will be working on a proof and discover that they have a line of reasoning that will work if some other claim is true. Encourage the student to develop their main argument and then return to see if they can fill in the missing link. A claim that is not a focus of your interest, but which you need for a larger proof, is called a lemma. As students working on a common problem share their discoveries through oral and written reports, they may recognize that a fellow researcher has already proven a needed lemma. Alternatively, they may realize that their conjecture is a straightforward consequence of a general result that another classmate has proven. We call a theorem that readily follows from an important result a corollary. These events contribute enormously to students’ understanding of mathematics as a communal activity.

There are many well-known cases of theorems that mathematicians have proven pending some other result. Of course, that means that they are not actually theorems until the lemma has been established. What is a theorem in these situations is the connection between two unproven results. For example, Gerhard Frey proved that if a long-standing problem known as the Taniyama-Shimura conjecture were true, then Fermat’s Last Theorem (MacTutuor) must be as well. This connection inspired Andrew Wiles to look for a proof of the Taniyama-Shimura conjecture.

WHEN IS A PROOF FINISHED?

How do we know that we have proven our conjecture? For starters, we should check the logic of each claim in our proof. Are the premises already established? Do we use the conclusions to support a later claim? Do we have a rigorous demonstration that we have covered all cases?

We next need to consider our audience. Is our writing clear enough for someone else to understand it? Have we taken any details for granted that our readers might need clarified? Ultimately, the acceptance of a proof is a social process. Do our mathematical peers agree that we have a successful proof? Although we may be confident in our work, unless others agree, no one will build upon or disseminate our proof. Our theorem may even be right while our proof is not. Only when our peers review our reasoning can we be assured that it is clear and does not suffer from logical gaps or flaws.

If a proof is unclear, mathematical colleagues may not accept it. Their clarifying questions can help us improve our explanations and repair any errors. On the other hand, mathematical truth is not democratically determined. We have seen many classes unanimously agree that a false assertion was true because the students failed to test cases that yielded counterexamples. Likewise, there have been classes with one voice of reason trying to convince an entire class of non-believers. The validity of a proof is determined over time—readers need time to think, ask questions, and judge the thoroughness of an exposition. Students should expect to put their proofs through the peer review process.

When do peers accept a proof? When they have understood it, tested its claims, and found no logical errors. When there are no intuitive reasons for doubting the result and it does not contradict any established theorems. When time has passed and no counterexamples have emerged. When the author is regarded as capable ("I don’t understand this, but Marge is really good at math"). Some of these reasons are more important than others, but all have a role in practice.

See Davis and Hersh’s (1981) The Mathematical Experience for a fine collection of essays on the nature of proof, on methods of proof, and on important mathematical conjectures and theorems.

How to End a Proof

Since one reason we tackle proofs is for the challenge, we are entitled to a modest "celebration" when a proof is completed. The nicest honor is to name a theorem after the student or students who proved it. If you dub proofs after their creators (e.g., Laura’s Lemma or the Esme-Reinhard Rhombus Theorem) and have them posted with their titles, students will be justifiably proud. Give conjectures titles, as well, in order to highlight their importance and as a way to promote them so that others will try to work on a proof.

Introduce students to the traditional celebration: ending a proof with "Q.E.D." Q.E.D. is an acronym for "quod erat demonstrandum," Latin for "that which was to be demonstrated." At the end of a proof by contradiction, students can use "Q.E.A.," which stands for "quad est absurdum" and means "that which is absurd" or "we have a contradiction here." These endings are the understated mathematical versions of "TaDa!" or "Eureka!" Modern, informal equivalents include AWD ("and we’re done") and W⁵ ("which was what we wanted") (Zeitz, p. 45). We have also seen "" and "MATH is PHAT!" at the end of student proofs. Professional publications are now more likely to end a proof with a rectangle () or to indent the proof to distinguish it from the rest of a discussion, but these are no fun at all.

Do remind students that once their celebration is over, their work is not necessarily done. They may still need to explore their theorem further to understand why it is true and not just that it is true, to come up with a clearer or more illuminating proof, or to extend their result in new directions. Additionally, proofs sometimes introduce new techniques that we can productively apply to other problems. In other words, the completion of a proof is a good time to take stock and figure out where to go next in one’s research. Like movies that leave a loose strand on which to build a sequel, most math problems have natural next steps that we can follow.

WRITING PROOFS

We are not very pleased when we are forced to accept a mathematical truth by virtue of a complicated chain of formal conclusions and computations, which we traverse blindly, link by link, feeling our way by touch. We want first an overview of the aim and of the road; we want to understand the idea of the proof, the deeper context. - Hermann Weyl (1932)

The standard form for a mathematical proof is prose interwoven with symbolic demonstrations and diagrams. Students who write paragraph explanations will often comment that they do not yet have a "real proof." However, the two-column style that they believe to be the only acceptable format is often not as clear or informative as a proof with more English in it. Encourage them to add narrative to their proofs and to use whatever form seems most effective at communicating their ideas. Let them know that written language is a part of mathematics.

Weyl encourages us tell the story of our proof at the start so that each step in the presentation can be located on that roadmap. We should be able to say to ourselves "Oh, I see why she did that. She is setting up for this next stage" rather than "Where on Earth did that come from? Why did she introduce that variable?" Our goal is not to build suspense and mystery, but to provide the motivation for the important steps in our proofs. As noted earlier, we improve a lengthy proof’s story by considering how the pieces of the proof fit together into connected chunks that we can present as separate theorems or lemmas. These chapters in the story reduce the number of arguments that our readers have to manage at any given stage in their effort to understand our proof.

Published proofs are often overly refined and hide from the reader the process by which the mathematician made her discoveries. As teachers, we want to encourage students to share the important details of that process. What methods did they consider? Why did some work and others not? What were the examples or special cases that informed their thinking? What dead ends did they run into? The teacher mentioned above, who disliked proof, was frustrated because the proofs that he had read were too polished to be a guide for how to develop a proof. The more we include our data, insights, experimentation, and derivations in our proofs, the more they will help others with their own mathematics.

We want to find a balance between the desire to convey the process of discovery, which is often circuitous, and the need to present a coherent argument. Students should develop an outline for each proof that reflects which ideas are dependent on which others. They should punctuate their narrative with clearly labeled definitions, conjectures, and theorems. Proofs should include examples that reveal both the general characteristics of the problem as well as interesting special cases. Examples are particularly helpful, not as a justification, but because they provide some context for understanding the more abstract portions of a proof. Examples may also help clarify imprecise notation or definitions.

Some additional recommendations for making proofs more readable:

• Define, in words, exactly what a variable or function represents when you introduce it. If your work involves a number of variables, you may want to make a legend to which readers can conveniently refer.
• Choose mnemonic variable names (e.g., p for perimeter or c₂ for a second coefficient) and do not feel limited to single letter names for functions or variables (although long names do make it more difficult to read complicated expressions).
• Be sure that the words that you use have unambiguous mathematical meaning. If a word is not a familiar mathematical term, provide a definition. For example, a pair of students working on the Raw Recruits project wrote to their mentor that they were investigating "How many ways can they do it wrong but still feel that they are right in a line of six recruits." Their mentor wrote back requesting clarification of the terms "right" and "wrong." They were able to be more precise, stating that a configuration of recruits was wrong if the recruits were not all facing in the same direction but seemed right if each recruit was facing either open space or another recruit’s back. (See the Connect the Dots teaching notes for another example).

If any parts of your research were carried out collaboratively or based on someone else’s thinking, be sure to acknowledge their work and how you built upon it. For a full discussion on how to write up your results, see Writing a Report in Presenting Your Research.

EVALUATING PROOFS

We evaluate proofs at several levels. First, we need to see if we can understand what the proof says. If our mathematical background is sufficient to understand the proof, then, with effort, we should be able to make sense of it (see Reading Technical Literature in Getting Information). Next, we want to decide whether the proof is actually a successful proof. Do all of the pieces fit together? Are the explanations clear? Convincing? A good proof does not over-generalize. If a proof does not work in all cases, is it salvageable for some meaningful subset of cases?

Students should be given time to read each other's proofs. They should be skeptical readers who are trying to help their classmate improve their work. They should be supportive by offering helpful questions about claims that are unclear or steps that would improve the proof. The writer of a proof should expect to address any concerns and to work through several drafts before the class declares her work completed. Although we are tempted to believe in our own discoveries, we are also obliged to look for exceptions and holes in our reasoning and not leave the doubting just to our peers.

Once a proof passes the first hurdle and we believe it is correct, we come to a different set of criteria for judging proofs. These criteria are both aesthetic and functional and help us to understand why we would want to find different ways to prove a particular theorem. Here are some considerations that students might apply to proofs that they study (see Evaluating Conjectures for further considerations):

• Does the proof use clear language? Are ideas presented in a logical order or is the structure of the proof problematic?
• Does the author use symbols in a way that strengthens their argument? Did they provide diagrams and examples when needed?
• Does the proof provide insight into the question? Does it make a surprising connection between two ideas or problems?
• Are the methods new or applied in a creative way? For example, did the author use symmetry that might not have been initially apparent?
• Is the proof interesting? Do the ideas of the proof appeal to you visually or in some abstract way because of the patterns involved?
• Does the proof lead to other theories or generalize to solve other questions? How broad is its impact? Does it open new avenues for our investigation?

Each of us has our own aesthetic for which areas of mathematics and ways of solving problems are most appealing. Mathematicians will often call a proof "elegant" or "kludgy" based on their standards of mathematical beauty. Is a substitution, offered without motivation, that quickly resolves a problem (e.g., let f(x) = cotan(1 – ^x/₂)) magical, concise, or annoying? Whichever of the standards above move us to call a proof beautiful, it is an important recognition that judgments of beauty are part of mathematics. Share your own aesthetics with students and encourage them to develop their own. It is perfectly reasonable simply to enjoy geometric or number theoretic problems and solutions more than some other area of mathematics. Some students may love problems that start out complicated but then sift down to simple results. Help them to recognize and celebrate these interests while broadening their aesthetics through the sharing of ideas with each other.

Class Activity: One way to highlight the different characteristics of proofs is to ask students to study and compare alternative proofs of the same theorem. Handout Three Proofs that is irrational (table 1, below) and give students time to read all three slowly (note: students should be familiar with proof by contradiction). Ask them to write down questions that they have about the different steps in the proofs. Next have them work in small groups trying to answer the questions that they recorded and clarify how each proof achieves its goal. Have each student then write an evaluation of the proofs: Does each proof seem to be valid? If not, where do they identify a problem? Which proof appealed to them the most? Why? Ask them to consider the other criteria above and choose one or more to address in evaluating the proofs.

Students may note that there are similarities among the proofs. All three proofs are indirect and all three begin by eliminating the root and converting the problem to one of disproving the possibility that . These first steps reduce the problem to one involving only counting numbers instead of roots and remove the likelihood that any not-yet-proven assumptions about roots or irrational numbers will creep into the reasoning.

Table 1. Three Proofs that is Irrational

Students are drawn to different parts of the three proofs. Some prefer Proof B because it does not rely on the assumption—kids may call it a gimmick—that a and b have no common factors. This objection is a good occasion to discuss the "story" of how that assumption comes into proofs A and C. It is essential to establishing the contradiction later on in the proof, but how did the prover know it was needed? The answer is that they didn’t and that it was put in place once the need was discovered (we have watched students develop this proof themselves and then stick in the condition in order to force the contradiction). If the authors of these proofs included details of their derivations—the story of how they thought up the proofs—they would avoid the discomfort that the austere versions create.

Proof C relies on a case-by-case analysis that the different ending digits cannot match. Again, despite the bluntness of its means, it seems to explain why cannot reduce to 2. This method becomes more elegant with fewer cases when we look at the final digit in a smaller base such as base 3.

The point of the above discussion is not to have your students choose one "best" proof, but to have them weigh the pros and cons of each. We want them to discover that not everyone in the class has the same mathematical tastes. However, some criteria are more objective than others. For example, one important criterion is how easily a proof may be generalized to related problems. In the case of the three proofs in table 1, you may ask students to decide which extend readily to show that the roots of other integers (or all non-perfect squares) are irrational. We might also inquire why the same proof methods do not show that is irrational.

Another objective criterion is the sophistication of the mathematics needed to support a proof. Proof A requires fewer lemmas than the other two. Despite students’ frequent preference for proof B, it relies on the comparatively "heavy machinery" of the fundamental theorem of arithmetic (positive integers have a unique prime factorization). Mathematicians often applaud a proof that uses more elementary methods, but, in this case, the elementary approach is not necessarily easier to understand.

You can introduce the activity described above with other accessible theorems. Pythagorean Theorem and its Many Proofs (Bogomolny) and Pythagorean Theorem (Weisstein) provide several dozen different proofs of the Pythagorean Theorem. Make handouts of a variety of these proofs and have each student pick three to study. Which did they like best? Why? Do they prefer those that involved geometric dissections or algebraic calculations? Those that were shorter and skipped steps or those that explained each step carefully? Can the class provide the missing arguments for the less rigorous "proof without words" diagrams? Encourage them to see the particular appeal of each proof.

PRACTICE PROOF ACTIVITIES

Earlier in this section, we suggested that students’ proof experiences are most effective when they emerge organically from student investigations. Nevertheless, for a number of reasons, there is value to students practicing creating proofs as well. For example, practice helps students hone techniques and instincts that they can use in work that is more open-ended. Additionally, some of the reasons given in Why Do We Prove? remain relevant even if we are told what to prove. When students share their proofs with each other, they get further practice reading proofs and comparing the different types of reasoning used to justify theorems.

The transfer of understandings derived from practice problems is particularly likely if the practice is not overly structured. Proof exercises not connected to the study of a particular content area (e.g., triangle congruence or induction) force students to think about which of their many skills might help solve the problem. For each one, they might ask, "Should we introduce a variable? Will an indirect proof work?" This way, they are practicing methods and making thoughtful choices. If students do not a have a clear reason for choosing one approach over another, point out to them they do not have to be paralyzed in the face of this uncertainty. They can just start experimenting with different representations of the information and different proof methods until one of them works.

Students’ first proofs are rarely polished or precise. They may over-emphasize one point while omitting an important consideration (see, for example, the student proof below). Without experience devising symbolic representations of their ideas, students’ representations are often inefficient or unhelpful. For example, a student working on the Amida Kuji project was asked by her teacher to clarify and strengthen an English argument using symbols. She devised substitutes for her words ("h_i is a horizontal rung"), but the symbols had no value facilitating her computations and led to an argument that was more difficult to read. The proof had that "mathy" look to it, but, until the student had a better grasp of the underlying structures of the problem and their properties, she was in no position to develop a useful system of symbols.

When we respond to students’ early proofs, our emphasis should be on the proof’s clarity and persuasiveness. Their arguments may take many forms: paragraphs, calculations, diagrams, lists of claims. Any of these may be appropriate. We want to help them identify any assumptions or connections that they have left unstated, but we also have to judge how convincing and complete a line of reasoning has to be. Can steps that are obvious be skipped? To whom must they be obvious? Does a proof have to persuade a peer, a teacher, or a less knowledgeable mathematics student? We want to help younger students develop rigor without bludgeoning them on specifics that they may not be ready to attend to. Can students adopt the attitude of the textbook favorite, "we will leave it as an exercise for the reader to verify that…" ? Fine readings on this topic include "I would consider the following to be a proof…" and "Types of Students’ Justifications" in the NCTM Focus Issue on the Concept of Proof (1998).

One answer to the above questions is that a student’s classmates should be able to understand and explain their proofs. If classmates are confused, they should explain where they lose the thread of an argument or what they think a sentence means so that the author can rewrite her proof to address these confusions. Once a proof has passed the peer test, we can note additional possible refinements that will help our students develop greater sophistication in their thinking and presentation over time. Try to focus on certain areas at a time and expand students’ rigor and use of symbols incrementally. We try to emphasize proper vocabulary first (see Definitions). The development of original and effective symbolic representations tends to take more time to appear.

Be aware of "hand-waving" in proofs. Hand-waving is what a magician does to distract his audience from a maneuver that he does not want them to notice. For mathematicians, hand-waving is a, perhaps unintentional, misdirection during a questionable part of an argument. The written equivalent often involves the words "must" or "could" (e.g., "the point must be in the circle…" ) without justification of the claimed imperative. Sometimes we need to note, but accept, a bit of hand-waving because a gap is beyond a students’ ability to fill.

Many of the proof exercises provided here are more suitable for high school than middle school students. The whole class settings described below as well as practice problems 1, 4, 6, 7, 15, and 16 are likely to work with middle school students (although others may also be useful depending on the students’ background). Particularly with younger students, doing proof within explorations that help them see how a proof evolves naturally from questions and observations is more valuable than exercises that ask them to prove someone else’s claims. When we are given a "to prove", we have to go back and explore the setting anyway in order to develop some intuition about the problem. Older students, who have a broader array of techniques from which to choose, are more likely to benefit from proof exercises.

Once a class has proven theorems in the context of longer research explorations, you can use the practice problems as a shorter activity. Choose a few problems to put on a handout and distribute them to each student. Give the students a few days to work on the problems and then discuss and compare their discoveries and proofs. Based on these discussions and peer responses, each student can then rewrite one of their proofs to produce a polished solution.

Kids need more experience trying to prove or disprove claims without knowing the outcome ahead of time. In genuine mathematical work, we pose a conjecture, but we are not sure that it is true until we have a proof or false until we have a counterexample. The practice problems below sometimes call attention to this indeterminate status by asking students to "prove or disprove" the claim. Some of them actually ask for a proof even though the claim is false. We include these red herrings because students are often overly confident about their own conjectures and need to develop greater skepticism. Students should not consider this feature foul play, but good training in skeptical thinking. We are often taught to see texts as unerring authorities, but even the most prestigious journals of mathematics and science occasionally publish results that turn out to be false or incomplete. We have found that students are delighted when, and will put great effort into proving that, a textbook or teacher is wrong. We are simply building in that opportunity.

Once a false statement has captured students’ attentions, challenge them to turn it into a true claim. Can they identify a significant set of cases for which the claim is true (e.g., by changing the domain to remove the counterexamples, see problem 10)? Can they generalize the claim (e.g., problem 7 is false, but the more general claim for two relatively prime divisors is true)?

A setting for whole class practice

The related games Yucky Chocolate and Chomp are good settings for early work with proof. These games are effective with both middle and high school classes. Both games begin with an n-by-m array of chocolate squares (n not necessarily different from m) in which the top left square of chocolate has become moldy.

Rules for the game of Yucky Chocolate: On each turn in the game of Yucky Chocolate, a player chooses to break the bar of chocolate along a horizontal or vertical line. These breaks must be between the rows of squares (figure 3). The rectangle that is broken off is "eaten" by that player. The game continues with the rectangle that includes the yucky square. You can introduce this game with real chocolate, but the incentive to break off large pieces for consumption may overwhelm any other strategic thinking. Players take turns until one player, the loser, is left with just the yucky piece to eat.

Figure 3. A horizontal break in the game of Yucky Chocolate leaves a 2 by 4 board

Introduce your class to the rules of the game and then have them pair off to play several rounds starting with a 4 by 6 board. They can play the game on graph paper, mark off the starting size of the chocolate bar, and then shade in eaten portions each turn. After a few rounds of play, students will start to notice winning end-game strategies. In one fifth-grade class, the students observed that when a player faced a 2-by-2 board, they always lost. Given that observation, additional play led them to see why a 3-by-3 board was also a losing position. They were able to turn these conjectures into theorems with simple case-by-case analyses. For the 3-by-3 board, the symmetry of the situation meant that there were really only two distinct moves possible (leaving a 2-by-3 or 1-by-3 board). Each of these moves gave the other player a winning move (reducing the board to a 1-by-1 or 2-by-2 case).

After the class realized that the smaller square positions were losers, some students took the inductive leap to conjecture that all n-by-n boards represented losing positions. One girl, who had never studied proof by induction, excitedly began explaining how each larger square array could be turned into the next smaller one and that she could always force the game down to the proven losing square positions. She had an intuitive understanding of the validity of an inductive argument. She then stopped and realized that her opponent might not oblige her by carving off just one column and that she did not know how big the next board might be. She had cast doubt on the reasoning of her own argument. She was facing another form of inductive proof in which one builds not just from the next smallest case but all smaller cases. After a while, the class was able to show that regardless of the move that an opponent facing an n-by-n board takes, there was always a symmetrical move that made a smaller square board. Therefore, they could inexorably force a win. This argument made it possible for a full analysis of the games that led to a win for the first player (n m) and those that should always be won by the second player.

Once students have a complete understanding of Yucky Chocolate, the game provides a nice opportunity for practicing problem posing. Ask the students to each develop one or more variations of the game. What characteristics can they change? Does the game remain interesting? Does it become more complicated? Do they have to change any rules to make it still make sense? Some of the changes that students have explored include moving the location of the moldy square, making the problem three-dimensional, changing the number of players, or playing with a triangular grid of chocolate.

Rules for the game of Chomp: The game of Chomp starts with the same slightly moldy chocolate bar, only the players take turns biting the chocolate bar with a right-angled mouth. These bites remove a chosen square and all remaining squares below and/or to the right of that square (figure 4. See Joyce for further examples).

Figure 4. Two turns in a game of Chomp

These bites can leave behind boards with complicated shapes that make it difficult to analyze which player should win for a given starting board. Student investigations can identify many sets of initial configurations (e.g., the 2-by-n or n-by-n cases) where a winning strategy can be determined and a proof produced (see Keeley And Zeilberger). Zeilberger’s Three-Rowed Chomp provides an elegant existence proof that the first player in a game must always have a winning strategy. Being an existence proof, it provides no hint at how the winning strategy might be found. See Gardner, Joyce, Keeley, and Stewart for more on the game of Chomp. The article by Stewart also discusses Yucky Chocolate. The Keeley article provides a lovely discussion of one class’s definitions, conjectures, and theorems about the game of Chomp.

Other Whole Class Problems and Resources

• Carmony (1979) presents the following setting: n people are standing in the plane and the distances between all pairs of individuals are distinct (no two alike). Each person is armed with a cream pie that they hurl at their nearest neighbor. Everyone’s throw is accurate. If the number of pie throwers is odd, what theorems can you state and prove about this situation?

  There are various possibilities. One is:

  Theorem: At least one person will not be thrown at.

  Proof: Let d_i be the distance the ith person is from her closest neighbor. Because all distances between the throwers are unique and because each distance is "owned" by two throwers, no more than two d_i can have the same value. If the largest d_i belongs to just one person (they are not the person closest to the person who is closest to them), that person will not be thrown at, because all other throwers have a nearer neighbor (due to their smaller d_i).

  If two people share the largest d_i, they will throw at each other (everyone else has a smaller d_i and will throw at someone else). Ignore those two mutually antagonistic throwers and apply our argument to the smaller problem of n – 2 throwers and n – 2 pies. For any arrangement of odd throwers, we will eventually encounter a thrower with a distinct largest d_i, in which case the claim is proven, or we keep ignoring pairs of isolated throwers (reducing the problem to a smaller set) until we are left with just one thrower who throws at someone else and is left unscathed.

  Corollary: At least one person must be hit at least twice.

  Proof: Since we have at least one clean thrower, there are more pies remaining than throwers and by the pigeonhole principle, at least one thrower must be hit by more than one pie.

  What is the smallest fraction of people that can be hit? Does this answer change for the one-dimensional case of n collinear people? For people floating in space? With 7 hurlers, the arrangement below (figure 5) results in all pies landing on the two throwers in the center. This establishes an upper limit for the two-dimensional answer at ²/₇.

  

  Figure 5. Seven pie throwers and just two targets

• Algorithms and Ice Cream for All (MegaMath) has a sequence of graph theory lessons with introductory proof experiences that are accessible to elementary students, but which are also of value for older students.
• Ron Knott’s Fibonacci Puzzles presents an impressive variety of settings that all generate the Fibonacci sequence. A sampling of these problems can be used to give students practice explaining the isomorphism between each setting and the series definition, F₀ = F₁ = 1 and F_n = F_{n – 1} + F_{n – 2}. The creation of such a mapping between two seemingly different problems is central to a great deal of mathematics. You can present these problems individually or along with others that do not generate the Fibonacci sequence so that students can discover the patterns for themselves. Once they conjecture which sequence is involved, they can try to prove the connection.

  As an example, consider the problem of the number of trains of length n that can be made from cars of length 1 and 2:

  n	Trains	Number of Trains
  1		1
  2	,	2
  3	, ,	3
  4	, , , ,	5

  We note that the first two values match the second and third Fibonacci terms. We can finesse this difference by noting that there is also 1 way to make a train of length 0 or we can just say that we are starting our series in a different place. How do we make all trains of length n? Well, each train must end with a single car or a double car. We make a length n train that ends with a single car by appending it to a train of length n – 1. We make a length n train that ends with a double car by appending it to a train of length n – 2. Thus, the number of ways to make such a train is the same as the number of n – 1 and n – 2 trains combined and this is just the recursive rule that defines the Fibonacci sequence.

• Our search for research problems and settings does not have to take us away from the standard curriculum. For example, students can discover and prove many theorems about quadrilaterals. This process can provide ample practice learning and applying definitions, using the triangle congruence theorems, and converting English conjectures into symbolic statements to prove.

Rather than work through an exploration of each quadrilateral type sequentially, provide the class with standard definitions of each and have them draw (or construct) examples of each. Point out that each shape has a number of properties that are a consequence of their definition (e.g., reflection symmetry) that are not explicitly part of their definition. The handout Quadrilateral Properties will encourage a systematic exploration of these properties, each of which can be turned into a conjecture (e.g., "if the diagonals of a quadrilateral are congruent and bisect each other, then the figure is a rectangle" or "if a figure is a rhombus then it is a parallelogram") that students can try to prove (see writing conjectures for more on this topic). For each proof, they should produce a labeled diagram and a statement of the given information in terms of those labels. The given information should be strictly limited to that provided in the definitions of the terms in the premise of the conjecture.

Once students have generated a number of proofs using the above activity, they can move on to explore the properties of the perpendicular bisectors or midpoints of the sides or the bisectors of the angles of the different quadrilaterals. They might even explore dividing the angles or sides into multiple equal parts (n-secting them). Dynamic geometry programs, such as Geometer’s Sketchpad, are particularly helpful in creating clear diagrams and taking accurate measurements that aid students in making discoveries with these settings.

• See Proofs In Mathematics (Bogomolny) for a discussion of proof and many nice proof examples and problems.

Proof Without Words

Diagrams play a complex role in mathematics. Many mathematicians think about even quite abstract ideas using visual images. Algebraic ideas often have natural geometric representations. We will often try to draw a picture of a problem that we are exploring because the image conveys a great deal of information organized according to a set of meaningful relationships. However, pictures do have limitations that students need to appreciate. In trying to gain insight from a diagram, we are restricted by its static nature. It shows us just one instance. The appeal of dynamic programs such as Geometer’s Sketchpad is, in part, that they allow us to quickly view multiple examples. Diagrams can mislead us if they are not created with precision and even accurate pictures may possess properties that are not typical of all cases. While diagrams may persuade and inform us, they do not constitute proofs. As with other types of examples, a picture may look convincing simply because we have not yet imagined how to construct a counterexample.

We want to help our students learn how to use diagrams as tools for furthering their investigations and how to extract information from them. As they work on problems, we can prompt them to consider whether a graph or other visual representation can be generated and studied. When they are reading other people’s proofs, encourage them to study all labels and features and to connect those details to the text and symbolic statements in the discussion—to see how they illuminate that discussion and whether they serve as an effective visual counterpart.

Students can also get practice interpreting diagrams by studying "proofs without words." These "proofs" are pictures that their author considers so enlightening that they readily convince us that we can dependably generalize the pattern to all cases. Depending on how wordless a proof without words is (and some do have the occasional accompanying text), the pictures can take some effort to analyze. Effective pictures can be the inspiration for a more formal proof. Winicki-Landman (1998, p. 724) cautions that some students may respond negatively to proofs without words if they feel that they will have to come up with such elegant diagrams themselves. Be sure to emphasize the value of working with diagrams and the purpose of these activities. When "proof pictures" do not even have variable labels, encourage students to choose variables for the different quantities in the picture and to see what the pictures tell them about those variables.

See Proof without words (Bogomolny) for further discussion and additional examples.

Some Problems

1. How does this diagram show that the sum of a positive number and its reciprocal is at least 2 (Nelson, p. 62):

   

2. What facts are suggested by the two pictures below? (Things that look like squares are.)



3. How do the pictures below "prove" that a² + b² 2ab?



 

Their Solutions

1. If the rectangles are congruent, then each has an area of x ^{. 1}/_x = 1. So, the area of the outer square is both (x + ¹/_x)² and 4 ^. 1 + (the area of the inner square). So long as the inner square exists, this equality yields the inequality (x + ¹/_x)² > 4. Taking the square root produces x + ¹/_x > 2 which was what we wanted. For what value of x will there be no inner square?
2. Possibilities include a² – b² = (a + b)(a – b) and a² > (a + b)(a – b). This latter interpretation is the picture that matches kids’ observations that, for example, 20² is greater than 21x19, 24x16, 23x17, or any other product of two distinct numbers equidistant from 20.
3. If the diagram on the left is a² + b², the challenge is to explain how we know that the rectangles on the right each have dimensions a and b. (The problem comes from Flores (2000))

Twenty Practice problems

Solutions to these problems are provided below as a way for you to gauge the difficulty of the problems and to determine their appropriateness for your class. Do not expect or require the student’s solutions to match the ones provided here. Alternatively, try to work on the problems yourself and with your students so that you can model how you think about analyzing problems and constructing proofs. After you and the students have your own results, you can use the solutions to make interesting comparisons. As the class discusses the different solutions to the problems, be sure to highlight the different methods (e.g., induction, proof by contradiction, case-by-case analysis) that they used. This emphasis will reinforce the message that there are common techniques that are often effective.

Once students have worked through some initial proofs, it is good to anticipate the frustrations and barriers that they will face as they attempt longer and harder problems. The NOVA (1997) video The Proof, which details Andrew Wiles’ work on Fermat’s Last Theorem, provides a motivational lesson that also tells students about one of the great mathematics accomplishments of the past century. Although Wiles’ proof is intimidating in its inaccessibility, his personal struggle and emotional attachment to the task are inspiring. After watching the video about his seven-year journey, students have a greater appreciation for the role that persistence plays in successful endeavors. The article Ten lessons from the proof of Fermat’s Last Theorem (Kahan) can be used as a teachers’ guide for a follow-up discussion. See Student and Teacher Affect for a further discussion of motivational considerations.

Note: Some of these problems may ask you to prove claims that are not true. Be sure to approach each with some skepticism—test the claims and make sure that a proof attempt is called for. If you disprove a statement, try to salvage some part of the claim by changing a condition.

1. Without appealing to Fermat’s Last Theorem, prove that there do not exist prime numbers a, b, and c, such that a³ + b³ = c³.
2. Prove that the number of faces of a polyhedron is less than or equal to the number of vertices.
3. Prove or disprove: For all integers n > 1, 2ⁿ⁺¹ < 3ⁿ.
4. 25 students are sitting in a 5 x 5 array of seats. Is it possible for them to change seats so that each student ends up in an adjacent seat in front of, behind, or to the side of their original seat? Prove your answer.
5. Prove that 8 divides 9^k – 1 for k 1.
6. An urn is filled with 75 white beads and 150 black ones. A pile of black beads abuts the urn. Remove two beads from the urn. If one is black, put back the other (white or black). If both are white, put back a black one from your pile. Each time you repeat this process, there will be one less bead in the urn. What will be the color of the final bead left in the urn?
7. Prove that if a number is divisible by 10 and is also divisible by 15, then it is divisible by 150.
8. These three problems are related:
   1. Prove or disprove. If true, characterize all such numbers that match the description: A whole number can have all odd factors.
   2. Prove or disprove. If true, characterize all such numbers that match the description: A whole number can have one quarter of its factors even.
   3. Let p(N) = the portion of factors of whole number N that are even. What values are possible for p(N)?
9. Prove that for five points, no three of which are collinear, there will always be four that form a convex quadrilateral.
10. Prove that any subset of n + 1 different counting numbers taken from the set S = {1, 2, 3, …, 2n} will include a pair that are not relatively prime. (Numbers are relatively prime when they have no common factors.)
11. Prove that any subset of n + 1 different counting numbers taken from the set S = {1, 2, 3, …, 2n} will include a pair that are relatively prime.
12. Prove that if two n-gons (n > 3) have n – 1 vertices in common, then the convex hulls of those n-gons must have at least two sides in common. (In two dimensions, the convex hull of a finite set of points will be the convex polygon of smallest area that contains all of the points. The vertices of the polygon will be points of the set. The more general definition in all dimensions and for sets of any size is the intersection of all convex sets containing the set.)
13. Each square of a 3 x 7 grid is colored either red or black. Prove or disprove: Any such coloring will include at least four squares of the same color that form the corners of a rectangle.
14. Prove or disprove: An integer consisting of 3ⁿ identical digits is divisible by 3ⁿ.
15. An m x n rectangle is made from mn unit squares. A diagonal of the rectangle passes through the interior of how many of these squares?

    

16. Is it possible to add and subtract the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9 each used exactly once (along with 8 intervening addition and subtraction signs) to arrive at a total of 10? If so, provide an example. If not, prove why not.
17. Choose a set of five points in the plane with integer coordinates. Consider the midpoints of each of the segments with endpoints chosen pair-wise from this set. Is it possible to choose the five points such that no midpoint has integer coordinates. If so, provide an example. If not, prove why not.
18. Consider permutations (different orders) of the numbers 1 through n. Let’s give each permutation a score that tells how many of the adjacent pairs in the list have the larger number to the right. For example, for the list {3, 1, 4, 2, 5}, we have the comparisons 3 > 1, 1 < 4, 4 > 2, and 2 < 5. The right-hand value is larger in two of these pairings, so the list gets a score of 2. Let A_n be the average score for all lists of length n. Show that there are as many lists of length n with a score less than A_n as there are lists with a score greater than A_n.
19. Three numbers m, n, and p have the property that m divides n, n divides p, and p divides m. What must be true about these numbers? Prove your conjecture.
20. Given two distinct real numbers, x and y, prove that the following three statements are interchangeable:
    1. x is greater than y.
    2. The mean, (x + y)/2, is less than x.
    3. The mean, (x + y)/2, is greater than y.

Sample solutions to the Practice Problems

1. Consider two different cases:
   1. a, b, and c are all odd. This is not possible (we leave it as an exercise for the reader to explain why not!).
   2. Given your reason for i) above, there must be at least one even among a, b, and c. 2 is the only even prime. Let’s consider the two possibilities: a or b is 2 (by symmetry, these are the same case) or c is 2. A not-very-exhausting exhaustive search of all small perfect cubes less than 8 shows that no two of them add up to 8, so c cannot be 2. If a or b were 2, we would need two perfect cubes that differ by 8. But the smallest difference between any two odd counting numbers (no less odd primes) is 3³ – 1³ = 26, so there is no solution. (Note: we could more rigorously defend this last claim by showing that (2n + 3)³ – (2n + 1)³ is strictly increasing).
2. The claim is false. Counterexamples include the regular octahedron and regular icosahedron. Are there specific conditions that we could add to make the claim true?
3. Students begin by generating some confirming data. It becomes clear that once the right side is larger, its more rapid growth will assure that it remains larger. An informal inductive student proof is: when n = 2, 8 < 9. Thereafter, the right side triples and the left side doubles, so the right side remains larger.

   Some students offer a more formal, but not necessarily more convincing, inductive proof: For our base case, n = 2, we have 8 < 9. Given 2ⁿ⁺¹ < 3ⁿ, multiply both sides by 2 to get 2ⁿ⁺² < 2^.3ⁿ. But, since 3ⁿ is always positive, 2^.3 ⁿ < 3^.3ⁿ or 3ⁿ⁺¹. Therefore, 2ⁿ⁺² < 3ⁿ⁺¹ which is the n + 1^st case.

   A non-inductive approach is possible: divide both sides of the original inequality by 2ⁿ to yield 2 < (3/2)ⁿ. The exponential expression on the right side increases with increasing n and is first greater than 2 when n = 2.

   What about using a graph of the functions on each side of the inequality? The right side looks like it is always higher, but it is easy to find cases of functions that eventually switch places again (e.g., graph the sides of 2ⁿ < 1000n²). Using a graph in this case is equivalent to looking at a large number of examples that do not provide a proof.

4. We can understand this situation by studying smaller cases. It is easy to find a reassignment that works for a 2 x 2 array:

   

   However, when we look for a solution to the 3 x 3 case, we always end up with an empty seat in a corner or the middle:

   

   We can use a parity argument to explain why a 5 x 5 rearrangement is not possible. Number the seats as shown in the array below. Each odd-numbered seat is bordered by even-numbered seats and vice versa. So, according to the rules, each student in an odd-numbered seat must end up in an even-numbered seat. However, there are 13 odd-numbered seats and only 12 even-numbered ones, so one odd chair must be empty and at least one even chair must have two, snuggling students.

   1	2	3	4	5
   6	7	8	9	10
   11	12	13	14	15
   16	17	18	19	20
   21	22	23	24	25

5. Students have solved this problem in a number of ways. Here are three variations:
   1. 9^k – 1 factors to (9 – 1)( 9^{k – 1} + 9^{k – 2} + 9^{k – 3} + … + 1). The first factor is 8 and the second factor is the sum of integers. Q.E.D.
   2. Prove the claim inductively:

      For k = 1, 9¹ – 1 = 8 which is divisible by 8.

      Assume that 9^k – 1 is divisible by 8. If so, then it equals 8m for some counting number m: 9^k – 1 = 8m

      We want to show that the divisibility of 9^{k + 1} – 1 follows, so let’s multiply by 9:

      9^{k +1} – 9 = 9(8m)

      We don’t want "– 9", so let’s add 8:

      9^{k +1} – 1 = 9(8m) + 8

      The right-hand side of this equation factors to 8(9m + 1), so 9^{k +1} – 1 is divisible by 8. Q.E.D.

   3. i. 9^k – 1 = (8 + 1)^k – 1

      ii. Expand (8 + 1)^k. How can I expand (8 + 1)^k ? The Binomial Expansion, which is a polynomial so arranged that the exponents of the powers of one term (8) decrease in magnitude, while the exponents of the powers of the second term (1) increase in magnitude.

      

      The expansion of the binomial is the sum of the products of the first term, the second term, and a coefficient. The exponents of the first term decrease from k to 0. The exponents of the second term increase from 0 to k. The coefficient increases in magnitude until it reaches the middle term, then decreases.

      The first term, a^k, has a factor of a in it because it is multiplication of a times itself k times. So the first term of the expansion has the first term of the binomial in it. Every term in between the first term and the last term is a product of a, b, and a coefficient. So all of these terms have factors of a and b in them. All these expansion terms have factors of both the first and second binomial terms.

      The last term of the expansion is just b^k, which only has a factor of b, or the second binomial term, in it.

      

      iii. All of the terms in the polynomial expansion have a factor of the first term, 8, except for the last term (because the exponent on the 8 was 0: 8⁰1^k).

      iv. So every term except for the last is divisible by 8, because having a factor of a number means it is divisible by that number.

      v. The last term in the expansion is 1^k = 1.

      vi. (8 + 1)^k – 1 = the binomial expansion above – 1. The – 1 cancels out the 1 (only term not divisible by 8) in the expansion.

      vii. 9^k – 1 = sum of terms which are all divisible by 8. Therefore, 8 divides 9^k – 1. Q.E.D.

      Note that this last student proof talked about the coefficients and an irrelevant behavior (increasing up to the middle term and then decreasing), but did not note the relevant consideration that these coefficients were integers. Unless the coefficients are integers, we cannot be sure that the factors of 8 remain in each term. The student was no doubt aware that the coefficients were integers, but may not have thought about the importance of that fact.

      This proof is longer than the others, but it was also clever in its use of the binomial theorem, which required recognizing that 9 could be split into two monomials. Responses to such a solution should note the creativity as well as highlight the particular technique, which might be useful for solving other problems. This proof is typical of good student work in that it reveals both sophisticated thinking and some still-missing understanding of a subtle idea (in this case, the domain requirements for the coefficients).

      What possibilities are there for generalization? All three proofs readily extend to show that n ^k – 1 is divisible by n – 1.

6. Clearly, we do not want to undertake simulations of this problem to see what happens at the end. We might start with a smaller number of beads to become more familiar with the rules and possible outcomes. Ultimately, we need to think about the two bead replacement rules. The first rule reduces the number of black beads by one, while leaving the number of white beads unchanged. The second rule increases the number of black beads by one, while reducing the number of white beads by two. So, we began with an odd number of white beads and will always have an odd number of white beads because we can only subtract two at a time (we are using both parity and invariance arguments here). When there is only one bead left, it must be white (because we can not have 0, an even number, white beads). The black bead total can also reach one, but there will still be at least one white bead left. (From Scientific American (March 1991), 116)
7. The claim is false. One counterexample is 30. The general claim that ab divides N, if a and b both divide N is true when a and b are relatively prime. The smallest N divisible by both a and b is the LCM(a, b). So N = k ^. LCM(a, b). If a and b have no common factors (i.e., are relatively prime), then the LCM(a, b) = ab and N = kab. Therefore, ab divides N.
8. To get a sense of the possibilities, we can start by picking numbers and looking at their factor sets. We see that the portion of evens is 0 for 9 and 15, ¹/₂ for 6 and 30, and ²/₃ for 12 and 36.

   A) This is true for all odd numbers. An odd number has all odd prime factors, combinations of which can only yield odd factors of the original number.

   B) No whole number has this property. To have any even factors, a number must have at least one factor of 2. For each odd factor of the original number, there is at least one matching even factor found by including the 2. For example, the factors of 30 are 1 and 2, 3 and 6, 5 and 10, and 15 and 30 with each odd factor having an even partner. Therefore, for an even number, at least one half of its factors must be even.

   C) For N = ^. (odd factors), p(N) = a/(a + 1). The a + 1 factors of are {1, 2, 4, 8, ..., } and a of these are even. For the remaining odd factors of n, multiplication by this set creates additional odd and even factors in this same proportion.

9. Let us break the problem down into different cases, each a different possible arrangement of the five points. Begin with the convex hull (the smallest convex region that includes the points) of the five points.

   i) If exactly four of the points are vertices of the hull, then they are the sought-after set.

   ii) If all five points are vertices of the hull (they define a convex pentagon), then any four of them will be form a convex quadrilateral.

   How do we know any four will suffice?

   Lemma: We will prove this claim indirectly. If we assume that a subset of four points, drawn from the vertices of a convex pentagon, make a non-convex quadrilateral, then one of the points, P, would lie in the interior of a triangle formed by the other three. The addition of the fifth point cannot affect P’s relationship with the other three points and so P must lie within the convex hull for all five points. However, that conclusion contradicts our given that all five were on the perimeter of the hull, so any subset of four points must also be convex.

   iii) If only three of the five points lie on the perimeter of the convex hull, then two are in the interior of the triangle made by those three. Construct the line containing those two interior points. It must pass through two of the sides of the triangle (it can’t pass through a vertex or we would have three collinear points). Discount the vertex that is an endpoint of those two sides (see diagram below—why a diagram now? Because we think our words will be clearer with it. We are also hopeful that a reader could have constructed the diagram herself). The remaining four points will form a convex quadrilateral. For a non-convex quadrilateral, each pair of opposite sides has a side whose extension intersects its opposite partner. For the four chosen points, the two from the triangle (A and B) were chosen because line DE, defined by the two interior points, did not intersect segment AB. Likewise, we know that an extension of segment AB will not intersect segment DE, because that segment is in the interior of the triangle (or any other convex figure) and the extensions of the sides of a triangle do not intersect the triangle’s interior. Therefore, The four points are not the vertices of a non-convex quadrilateral. (This was an informal indirect proof—do you see why?).

   

   iv) The above are the only three cases possible. The convex hull cannot be a segment or the five points would be collinear contradicting a condition of the theorem. (Adapted from Hoffman, 74.)

10. There are counterexamples to this claim: for example, the subset {1, 2, 3, 5} taken from the set {1, 2, 3, 4, 5, 6}. However, the theorem is salvageable if we add the condition n > 4. At most one of the n + 1 numbers can be even (two evens cannot be relatively prime), so the remaining n numbers must be all of the odds in the set. So once n is larger than 4, we have 3 and 9 in the set and they are not relatively prime.

    We can get a better bound on the number of relatively prime numbers possible. Let p be the number of distinct prime factors within the numbers from 1 to 2n. Two numbers will be relatively prime if they have none of those p factors in common. Therefore, we can have at most p + 1 different relatively prime numbers, the p primes (or powers of them) and 1. If we choose a number for our set that has more than one prime factor, that reduces the number we can choose before a pair has a common factor. The prime number theorem tells us that the number of primes up to a given number grows far more slowly than the original n + 1 limit.

11. A set of n + 1 distinct counting numbers less than or equal to 2n will include at least two numbers that are neighbors and these will be relatively prime. (Hoffman, 132.) Can you prove the claim that two of the numbers must be neighbors using the pigeonhole principle? Hint: make your holes the number pairs {1, 2}, {3, 4}, {5, 6}, …, {2n – 1, 2n}.
12. This claim is false. In the example below, the rust colored lines are two quadrilaterals with three vertices, A, B, and C, in common (D and E have been swapped). The shaded regions are the convex hulls and they have no sides in common. The challenge is to intentionally look for special cases and not confirming examples—to think about the leeway provided by the one point that is not common to the two figures.

    

13. No coloring is possible. No two columns can have the same pattern of colors, or whichever color appears at least twice will make the corners of a rectangle. Therefore, we need 7 different column patterns. If any column contains three black boxes, then no other column can have two black boxes or those two along with two of the original three will form the corners of a rectangle. An all-red column similarly restricts our choices. There are only 8 different possible columns (2 color choices in 3 spots) and 7 columns to fill, so we can only avoid one pattern. Therefore, we will have at least one all-red or all-black column as well as columns with two reds or blacks that complete a rectangle. What are the maximum widths for rectangle-free colorings for boards of height 2, 4, 5, etc.? What if you allow additional colors?

    

14. Let’s start with the base case for an inductive proof. When n = 0, we have a 1-digit number which is always divisible by 1. Assume all numbers with 3ⁿ identical digits are divisible by 3ⁿ. Numbers with 3ⁿ⁺¹ identical digits are three consecutive identical 3ⁿ-digit numbers catenated and are equal to

    .

    For example, 444444444444444444444444444 = (10¹⁸ + 10⁹ + 1)(444444444). The first factor above is an integer with three 1’s and (in all but one case) interspersed zeroes. Its digits sum to 3 so that factor is divisible by 3. Therefore, it contributes one more factor of 3 to the 3ⁿ contributed by the catenated number of 3ⁿ digits and we have a total factor of 3ⁿ⁺¹.

15. Let’s give our rule for the number of squares intersected by the diagonal a name, S(m, n). After drawing diagrams and gathering data for different combinations of m and n, we see some patterns. When we hold m constant, S is largest when m and n have no common factors. S is smallest when n divides m.

    The diagrams help us to understand the patterns: when m and n are relatively prime, the diagonal does not pass through vertices of the squares except for the two at its endpoints. If we trace the path of the diagonal, we see that it will only enter the interior of a new square when it crosses a horizontal or vertical line in the grid. It will cross m – 1 vertical grid lines and n – 1 horizontal grid lines. Since the diagonal begins in a square, it will intersect a total of 1 + (m – 1) + (n – 1) squares. So, when m and n are relatively prime (GCF(m, n) = 1),

    S(m, n) = m + n – 1.

    But when m and n have a common factor, the diagonal passes through vertices of the squares, which means it passes through horizontal and vertical grid lines at the same time and hits that many fewer interiors. The diagonal hits GCF(m, n) – 1 vertices within the rectangle which reduces the total number of squares hit to

    S(m, n) = m + n – 1 – (GCF(m, n) – 1) = m + n – GCF(m, n).

    We have a formula that works, but let’s back up a bit before we declare our proof complete. We made claims about the behavior of the diagonal for different m and n that we did not justify (except to point to the diagrams). How do we know that the diagonal will not pass through any vertices when m and n are relatively prime? The slope of the diagonal is constant and is ⁿ/_m. If the diagonal passes through an interior point (a, b), then we know ^b/_a = ⁿ/_m., with b < n and a < m. But, if m and n have no common factors, then the slope cannot reduce to an equal fraction and no such point is possible.

    

    If m and n have a common factor, k, then there are k – 1 points that are on the diagonal because they have the same ratio as m and n: (^m/_k , ⁿ/_k), (^2m/_k , ²ⁿ/_k), (^3m/_k , ³ⁿ/_k),…, (^(k–1)m/_k , ^(k–1)n/_k).

    We can also derive our full formula recursively. Once we have the formula for relatively prime cases, S(m, n) = m + n – 1, we look at the cases with m and n having a common factor k = GCF(m, n). The diagonal will pass through k smaller rectangles with relatively prime sides. Our total is, therefore,

    S(m, n) = k^.S(^m/_k, ⁿ/_k) = k(^m/_k + ⁿ/_k – 1) = m + n – k or m + n – GCF(m, n).

    This formula reduces to our special case formula when the greatest common factor is 1, so it covers all cases. Can students generalize this problem and solution to higher dimensions? To other grids?

16. We cannot add and subtract the numbers to yield 10. We again use parity arguments to support our proof. The sum of 1 through 9 is 45. If we choose to subtract some of these numbers rather than add them, then our total of 45 will be reduced by twice that value, because the value is no longer being added and it is being subtracted. Symbolically, we note that A + B is 2B greater than A – B. Therefore, we can only reduce our sum of 45 by even amounts and the total will always be odd. 10 is not odd and so is not attainable. (This problem was adapted from Erickson and Flowers.)
17. We can choose no more than 4 points that meet this condition. The midpoint has coordinates that are the average of the coordinates of the endpoints. The coordinate of a midpoint will be an integer only if the corresponding coordinates of the endpoints have the same parity (so that they sum to an even before being divided by 2). Therefore, we need five points, no two of which have coordinates with the same parity. There are only four possible combinations of odd and even x- and y-coordinates, so the task cannot be accomplished. (This problem was adapted from Erickson and Flowers.)
18. This problem poses a common challenge: to show that two sets are the same size. To do so, we do not have to know the actual size of either; we can instead establish a correspondence between the elements of the sets. Imagine having two large jars of jellybeans and wanting to know if the quantities are the same. You could count each jar separately and compare the totals or you could take one bean from each jar and put them aside in pairs. In the second case, you would not need to know how many pairs you removed, just whether one jar had any beans left after the other was empty. Likewise, we can compare two sets mathematically by establishing a pairing without having to determine the size of either set.

    As students explore this problem, they may need a way to systematically list all of the permutations of n numbers. They may know or need to discover that there are n! permutations for n elements.

    If we look at a list of all 4-element permutations and their scores sorted in numerical order (e.g., 2314 comes before 2431), we notice a symmetry to the scores. There is a 3 at the top, a 0 at the bottom of the list, and scores of 1 and 2 mirror each other:

    

    Next, we need to figure out what the connection is between the symmetrically located lists. How is 1432 related to 4123? Each is the 5’s complement of the other. That is, one list can be found by subtracting each element of the other list from 5. For an adjacent pair of elements, xy, if x < y, then – x > – y and 5 – x > 5 – y. Therefore, each adjacent pair that contributed to a permutation’s score will not contribute to the score for its complementary sequence and vice versa. Since each pair will contribute to either one sequence or the other, the total score for the two sequences will equal the number of adjacent pairs, n – 1, and the average score for that pair will be ^{(n – 1)}/₂. Each permutation is the 5’s complement of its 5’s complement (the operation is its own inverse) and so each has a unique partner. Since all permutations have one partner and all such pairings have the same average, then A_n = ^{(n – 1)}/₂. Since each pair also has this average, both lists within a pair will equal A_n or one will be greater and the other will be less than A_n. Therefore, there are as many lists above the average as below (which was what we wanted).

    There is an alternative correspondence possible. We can match each sequence, S, with its reversal, S'. If sequence S has a score of s, S' will have a score of n – 1 – s. There are n – 1 comparisons and each will contribute to the score for either a list or its reversal but not both (reversing the lists reverses the order of the inequalities). Therefore, the total of the scores for S and S' will be n – 1 and we can proceed as above.

19. The three numbers must be equal. Proof 1: If m divides n, n divides p, and p divides m, then there must be three whole numbers j, k, and l, such that . Multiply these three equations to yield . If the product of three whole numbers is 1, then all three equal 1. Since j, k, and l are all 1, the three rational equations above give us n = m, p = n, and m = p and so all three are equal.

    Proof 2: We can ignore some of the information in our givens and just draw from divisibility a simple inequality. Namely, if m divides n, then m n. Likewise, n p and p m. These latter two combine to give n m. The other two pairings of the inequalities yield m p and p n. We now have p n and n p, so n = p. With m n and n m, n = m. So n = p = m.

20. To show that two statements are interchangeable, we need to show that each implies the other. We cannot just prove the connection in one direction. To show that three statements are equivalent, we can show interchangeability pairwise or in a circle:
    

    A B:	B C:	C A:
    x > y
    		x > y

    This sequence suffices, because A B and B C gives us the A C we needed to go along with the C A that we proved directly. We can get the remaining two implications in a similar fashion.

BIBLIOGRAPHY

Printable Version (PDF)

Making Mathematics Home |
Mathematics Projects | Students | Teachers |
Mentors | Parents | Hard Math Café |