Proving theorems and special cases (Part 16): An old homework problem

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

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

Usually, the answer is no. In this series of posts, we’ve seen that a conjecture could be true for the first 40 cases or even the first $10^{316}$ cases yet not always be true. We’ve also explored the computational evidence for various unsolved problems in mathematics, noting that even this very strong computational evidence, by itself, does not provide a proof for all possible cases.

However, there are plenty of examples in mathematics where it is possible to prove a theorem by first proving a special case of the theorem. For the remainder of this series, I’d like to list, in no particular order, some common theorems used in secondary mathematics which are typically proved by first proving a special case.

The following problem appeared on a homework assignment of mine about 30 years ago when I was taking Honors Calculus out of Apostol’s book. I still remember trying to prove this theorem (at the time, very unsuccessfully) like it was yesterday.

Theorem. If $f(x)$ is a continuous function so that $f(x+y) = f(x) + f(y)$ , then $f(x) = cx$ for some constant $c$ .

Proof. The proof mirrors that of the uniqueness of the logarithm function, slowly proving special cases to eventually prove the theorem for all real numbers $x$ .

Case 1. $x = 0$ . If we set $x =0$ and $y = 0$ , then

$f(0+0) = f(0) + f(0)$

$f(0) = 2 f(0)$

$0 = f(0)$

Case 2. $x \in \mathbb{N}$ . If $x$ is a positive integer, then

$f(x) = f(1 + 1 + \dots + 1)$

$f(x) = f(1) + f(1) + \dots + f(1)$

$f(x) = xf(1)$ .

(Technically, this should be proven by induction, but I’ll skip that for brevity.) If we let $c = f(1)$ , then $f(x) = cx$ .

Case 3. $x \in \mathbb{Z}$ . If $x$ is a negative integer, let $x = -n$ , where $n$ is a positive integer. Then

$f(x + (-x)) = f(x) + f(-x)$

$f(0) = f(x) + f(n)$

$0 = f(x) + cn$

$-cn = f(x)$

$cx = f(x)$

Case 4. $x \in \mathbb{Q}$ . If $x$ is a rational number, then write $x = p/q$ , where $p$ and $q$ are integers and $q$ is a positive integer. We’ll use the fact that $p = xq = p/q \times q = p/q + p/q + \dots + p/q$ , where the sum is repeated $q$ times.

$f(p/q + p/q + \dots + p/q) = f(p)$

$f(p/q) + f(p/q) + \dots + f(p/q) = cp$

$q f(p/q) = cp$

$f(p/q) = cp/q$

$f(x) = cx$

Case 5. $x \in \mathbb{R}$ . If $x$ is a real number, then let $\{r_n\}$ be a sequence of rational numbers that converges to $x$ , so that

$\lim_{n \to \infty} r_n = x$

Then, since $f$ is continuous,

$f(x) = f \left( \displaystyle \lim_{n \to \infty} r_n \right)$

$f(x) =\displaystyle \lim_{n \to \infty} f(r_n)$

$f(x) = \displaystyle \lim_{n \to \infty} c r_n$

$f(x) = cx$

QED

Random Thought #1: The continuity of the function $f$ was only used in Case 5 of the above proof. I’m nearly certain that there’s a pathological discontinuous function that satisfies $f(x+y) = f(x) + f(y)$ which is not the function $f(x) = cx$ . However, I don’t know what that function might be.

Random Thought #2: For what it’s worth, this same idea can be used to solve the following problem that was posed during UNT’s Problem of the Month competition in January 2015. I won’t solve the problem here so that my readers can have the fun of trying to solve it for themselves.

Problem. Determine all nonnegative continuous functions that satisfy

$f(x+t) = f(x) + f(t) + 2 \sqrt{f(x)} \sqrt{f(t)}$ .

Proving theorems and special cases (Part 15): The Mean Value Theorem

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

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

6. Theorem (Mean Value Theorem). If $f$ is a continuous function on the interval $[a,b]$ which is differentiable on the interior $(a,b)$ , then there is a point $c \in (a,b)$ so that

$f'(c) = \displaystyle \frac{f(b)-f(a)}{b-a}$

In other words, there is a point $c$ in $(a,b)$ so that the slope of the tangent line at $c$ is the same as the slope of the line segment connecting the endpoints.

This is a consequence of the following lemma.

Lemma (Rolle’s Theorem). If $f$ is a continuous function on the interval $[a,b]$ which is differentiable on the interior $(a,b)$ so that $f(a) = 0$ and $f(b) = 0$ , then there is a point $c \in (a,b)$ so that $f'(c) = 0$ .

Notice that Rolle’s Theorem is really a special case of the Mean Value Theorem: if $f(a) = 0$ and $f(b) = 0$ , then the right-hand side of the conclusion of the Mean Value Theorem becomes

$\displaystyle \frac{f(b)-f(a)}{b-a} = \displaystyle \frac{0-0}{b-a} = 0$ ,

thus matching the conclusion of Rolle’s Theorem.

I won’t type out the proofs of Rolle’s Theorem and the Mean Value Theorem here, since Wikipedia has already done that very well. Suffice it to say that Rolle’s Theorem logically comes first, and then the Mean Value Theorem can be proven using Rolle’s Theorem. The main idea is to assume that the function $f$ satisfies the hypotheses of the Mean Value Theorem and then define

$g(x) = f(x) - f(a) - \displaystyle \frac{f(b)-f(a)}{b-a} (x-a)$

It’s straightforward to show that $g$ satisfies the hypotheses of Rolle’s Theorem and conclude that there must be a point so that $g'(c) = 0$ , from which we obtain the conclusion of the Mean Value Theorem.

Proving theorems and special cases (Part 14): The Power Law of differentiation

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

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

5. Theorem. For any rational number $r$ , we have $\displaystyle \frac{d}{dx} x^r = r x^{r-1}$ .

This theorem is typically proven using the Chain Rule (in the guise of implicit differentiation) and the following lemma:

Lemma. For any integer $n$ , we have $\displaystyle \frac{d}{dx} x^n = n x^{n-1}$ .

Clearly, the lemma is a special case of the main theorem. However, the lemma can be proven without using the main theorem:

Proof of Lemma (Case 1). If $n$ is a positive integer, then

$\displaystyle \frac{d}{dx} x^n = \displaystyle \lim_{h \to 0} \frac{(x+h)^n - x^n}{h}$

$= \displaystyle \lim_{h \to 0} \frac{x^n + n x^{n-1} h + \frac{1}{2} n(n-1) x^{n-2} + \dots + h^n - x^n}{h}$

$= \displaystyle \lim_{h \to 0} \left[ n x^{n-1} + \frac{1}{2} n(n-1) x^{n-2} h + \dots + h^{n-1} \right]$

$= n x^{n-1} + 0 + \dots + 0$

$= n x^{n-1}$

Case 1 can also be proven using the Product Rule and mathematical induction.

Proof of Lemma (Case 2). If $n = 0$ , then the theorem is trivially true since $x^0 = 1$ , and the derivative of a constant is zero.

Proof of Lemma (Case 3). If $n$ is a negative integer, then write $n = -m$ , where $m$ is a positive integer. Then, using the Quotient Rule,

$\displaystyle \frac{d}{dx} x^n = \displaystyle \frac{d}{dx} \left( x^{-m} \right)$

$= \displaystyle \frac{d}{dx} \left( \frac{1}{x^m} \right)$

$= \displaystyle \frac{0 \cdot x^m - 1 \cdot m x^{m-1}}{x^{2m}}$

$= -m x^{-m - 1}$

$= n x^{n-1}$

QED

Now that the lemma has been proven, the main theorem can be proven using the lemma.

Proof of Theorem. Suppose that $r = p/q$ , where $p$ and $q$ are integers. Suppose that $y = x^r = x^{p/q}$ . Then:

$y = x^{p/q}$

$y^q = \displaystyle \left[ x^{p/q} \right]^q$

$y^q = x^p$

Let’s now differentiate with respect to $x$ :

$q y^{q-1} \displaystyle \frac{dy}{dx} = p x^{p-1}$

$\displaystyle \frac{dy}{dx} = \displaystyle \frac{p x^{p-1}}{q y^{q-1}}$

$\displaystyle \frac{dy}{dx} = \displaystyle \frac{p}{q} \frac{x^{p-1}}{[x^{p/q}]^{q-1}}$

$\displaystyle \frac{dy}{dx} = \displaystyle \frac{p}{q} \frac{x^{p-1}}{x^{p - p/q}}$

$\displaystyle \frac{dy}{dx} = \displaystyle \frac{p}{q} x^{p-1 - (p-p/q)}$

$\displaystyle \frac{dy}{dx} = \displaystyle \frac{p}{q} x^{p - 1 - p + p/q}$

$\displaystyle \frac{dy}{dx} = \displaystyle \frac{p}{q} x^{p/q - 1}$

$\displaystyle \frac{dy}{dx} = r x^{r-1}$

QED

Proving theorems and special cases (Part 13): Uniqueness of logarithms

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

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

The next theorem is needed in calculus to show that $\ln x = \displaystyle \int_1^x \frac{dt}{t}$ .

4. Theorem. Let $a \in \mathbb{R}^+ \setminus \{1\}$ . Suppose that $f: \mathbb{R}^+ \rightarrow \mathbb{R}$ has the following four properties:

$f(1) = 0$
$f(a) = 1$
$f(xy) = f(x) + f(y)$ for all $x, y \in \mathbb{R}^+$
$f$ is continuous

Then $f(x) = \log_a x$ for all $x \in \mathbb{R}^+$ .

In other blog posts, I went through the full proof of this theorem, which is divided — actually, scaffolded — into cases:

Case 1. $f(x) = \log_a x$ if $x$ is a positive integer.

Case 2. $f(x) = \log_a x$ if $x$ is a positive rational number.

Case 3. $f(x) = \log_a x$ if $x$ is a negative rational number.

Case 4. $f(x) = \log_a x$ if $x$ is a real number.

Clearly, Case 1 is a subset of Case 2, and Case 3 is a subset of Case 4. Once again, a special case of a theorem is used to prove the full theorem.

Interesting calculus problems

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

The number of digits of n!: Index

I’m doing something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on computing the number of digits in $n!$ .

Part 1: Introduction – my own childhood explorations.

Part 2: Why a power-law fit is inappropriate.

Part 3: The correct answer, using Stirling’s formula.

Part 4: An elementary derivation of the first three significant terms of Stirling’s formula.

To prove that two things are equal, show that the difference is zero

The title of this post, “To prove that two things are equal, show that the difference is zero,” is surprisingly handy in the secondary mathematics curriculum. For example, it is the basis for the proof of the Mean Value Theorem, one of the most important theorems in calculus that serves as the basis for curve sketching and the uniqueness of antiderivatives (up to a constant).

And I have a great story that goes along with this principle, from 30 years ago.

I forget the exact question out of Apostol’s calculus, but there was some equation that I had to prove on my weekly homework assignment that, for the life of me, I just couldn’t get. And for no good reason, I had a flash of insight: subtract the left- and right-hand sides. While it was very difficult to turn the left side into the right side, it turned out that, for this particular problem, was very easy to show that the difference was zero. (Again, I wish I could remember exactly which question this was so that I could show this technique and this particular example to my own students.)

So I finished my homework, and I went outside to a local basketball court and worked on my jump shot.

Later that week, I went to class, and there was a great buzz in the air. It took ten seconds to realize that everyone was up in arms about how to do this particular problem. Despite the intervening 30 years, I remember the scene as clear as a bell. I can still hear one of my classmates ask me, “Quintanilla, did you get that one?”

I said with great pride, “Yeah, I got it.” And I showed them my work.

And, either before then or since then, I’ve never heard the intensity of the cussing that followed.

Truth be told, probably the only reason that I remember this story from my adolescence is that I usually was the one who had to ask for help on the hardest homework problems in that Honors Calculus class. This may have been the one time in that entire two-year calculus sequence that I actually figured out a homework problem that had stumped everybody else.

Newton vs. Leibniz

Source: https://www.facebook.com/AmerMathMonthly/photos/a.250425975006394.53155.241224542593204/755598191155834/?type=1&theater

A 100-Year old computer for computing Fourier transforms

From http://www.engineerguy.com/fourier/:

Many famous machines have been built to do math — like Babbage’s Difference Engine for solving polynomials or Leibniz’s Stepped Reckoner for multiplying and dividing — yet none worked as well as Albert Michelson’s harmonic analyzer. This 19th century mechanical marvel does Fourier analysis: it can find the frequency components of a signal using only gears, springs and levers. We discovered this long-forgotten machine locked in a glass case at the University of Illinois. For your enjoyment, we brought it back to life in this book and in a companion video series — all written and created by Bill Hammack, Steve Kranz and Bruce Carpenter.

A free PDF of their book is available at the above link; the book is also available for purchase. Here are the companion videos for the book.

Helping Mathematics Students Survive the Post-Calculus Transition

Every so often, I’ll publicize through this blog an interesting article that I’ve found in the mathematics or mathematics education literature that can be freely distributed to the general public. Today, I’d like to highlight Michael J. Cullinane (2011) Helping Mathematics Students Survive the Post-Calculus Transition, PRIMUS: Problems, Resources, and Issues in Mathematics Undergraduate Studies, 21:8, 669-684, DOI:10.1080/10511971003692830

Here’s the abstract:

Many mathematics students have difficulty making the transition from procedurally oriented courses such as calculus to the more conceptually oriented courses in which they subsequently enroll. What are some of the key “stumbling blocks” for students as they attempt to make this transition? How do differences in faculty expectations for students and student expectations for themselves contribute to the “transition dilemma?” What might faculty incorporate into students’ learning experiences during the transition to help students better navigate the shift from procedural to conceptual, from concrete to abstract? This article offers some lessons learned in connection with these questions.

The full article can be found here: http://dx.doi.org/10.1080/10511971003692830