A mathematical proof can be the size of a novella. For example, Andrew Wiles’s published his famous proof of Fermat’s Last Theorem in two journal articles covering 129 pages. But proofs in introductory textbooks like Rosen often contain just a few sentences. It might seem obvious that these proofs are short because they’re easy. But that’s not exactly right. Last week, I wrote a moderately long post covering an “easy” proof about how the div operator behaves when the first argument is negative. Why was it so much longer than the version in the solution guide?
Proof-writing skills are important for all college-level math. But there’s a special relationship between proofs and discrete math. In the “Goals of a Discrete Mathematics Course” section in the preface to his textbook, Rosen puts Mathematical Reasoning first in the list. He writes:
Students must understand mathematical reasoning in order to read, comprehend, and construct mathematical arguments [proofs]. This text starts with a discussion of mathematical logic, which serves as the foundation for the subsequent discussions of methods of proof. Both the science and the art of constructing proofs are addressed.
Rosen Chapter 1 is “The Foundations: Logic and Proofs,” and that chapter ends with sections on “Introduction to Proofs” and “Proof Methods and Strategy.” A textbook that specifically covers proof techniques, Daniel J. Velleman’s How to Prove It, begins with chapters on these same topics, and includes chapters on logic and on mathematical induction which Rosen also covers. So it’s not surprising that many of the exercises in Rosen ask for proofs. Here is a process I use to get the most out of these exercises.
If you search for advice on how to read a math textbook, you’ll find plenty to choose from. I’ll link to some of my favorites at the end of this article. But first, here’s an overview of my experience reading math books, and what techniques I found to be useful.
In their first 13 or so years of school, students cover a standardized math curriculum. Last week, I covered how Khan Academy approaches that curriculum. Notably absent from that list are many topics in discrete mathematics. But what is discrete mathematics, anyway? I’ll answer that in two ways: with a definition, and with a curriculum.
Khan Academy’s math program is designed to help children and young adults learn and practice a particular set of math skills. These skills map to school curricula like the US Common Core, so that when students learn something on the site, it translates to success in the classroom. But Khan Academy can also help adults review the fundamental skills necessary to learn more advanced math. The idea is to fill in “swiss cheese gaps” in knowledge that often accumulate when learning math in school. These gaps can slow down further learning, since math success in later courses depends on knowing the skills taught in previous courses.
This week, I’ll go over the topics available on Khan Academy. Next week, I’ll look at how they relate to discrete math topics.
The process of learning math involves mastering thousands of small skills. Khan Academy has exercises that help you practice the first 1500 or so of these skills. But as I discussed last week, the Khan Academy mastery system only gets you to an initial level of mastery. The topic for this week: how to continue using Khan Academy to increase your skill mastery after you have officially “mastered” the skill.
Before learning discrete math, it’s useful to know how much other math you remember. Last week, I discussed how Khan Academy is uniquely useful for evaluating and improving your skills in math topics through Calculus. But eventually you might reach Mastery level in all Khan Academy math skills. Does that mean it’s time to move on? Not quite.
Math builds on itself, so trying to learn a math topic without first mastering its prerequisites is just asking for trouble. A good place to learn prerequisites is Khan Academy. Although it’s missing many advanced math topics, it covers the basics well. And the way it organizes practice problems ensures that you regularly get tested on the concepts you need the most practice with.
Competitive programming practice sites often organize problems by topic area. For example, uHunt has categories for graphs, string processing, dynamic programming, and many others. uHunt Chapter 5 covers topics in mathematics. Since math is a separate field from computer science and algorithms (though it’s closely related), I’m considering this week how it relates to competitive programming preparation.