Proof by Induction with a Difficult Base Case

I’m teaching Discrete Mathematics this semester. It is our “intro to proofs” class. One of the proof techniques the students learn is proof by induction. I told the class that usually the base case for induction proofs are easy and that most of the work occurs in the inductive step. Indeed, most of the proofs that they see have base cases that are elementary to check (performing elementary calculations to conclude that 1=1, for instance). I warned them that this was not always the case. Sometimes the base case is the most difficult part of the induction proof.

I spent a while thinking about an example I could show them where this is the case. I found this Math Overflow link on this same question. They gave a few examples. Here’s one of them—the multi-function product rule for derivatives. The base case requires using the definitions of continuity and differentiability and the theorem that every function differentiable at a point is continuous at the point. It is not a simple “1=1” base case. The inductive step is much easier, although it is still not totally trivial because it requires using both the base case and the inductive hypothesis.

Theorem. Let f_1, f_2,\ldots, f_n be functions that are differentiable at some point c. Then (f_1 f_2\cdots f_n)^\prime(c)=\sum_{i=1}^n f_1(c)f_2(c)\cdots f_i^\prime(c)\cdots f_n(c).

Proof. This is a proof by induction on n. Let P(n) be the statement that given n differentiable functions f_1, f_2,\ldots, f_n, it follows that (f_1 f_2\cdots f_n)^\prime(c)=\sum_{i=1}^n f_1(c)f_2(c)\cdots f_i^\prime(c)\cdots f_n(c).

Base case: n=2. Let f_1 and f_2 be differentiable at c. Recall that because f_1 is differentiable at c, it is continuous at c. Then

\displaystyle(f_1f_2)^\prime (c)=\lim_{h\to 0}\frac{f_1(c+h)f_2(c+h)-f_1(c)f_2(c)}{h}

\displaystyle =\lim_{h\to 0}\frac{f_1(c+h)f_2(c+h)-f_1(c+h)f_2(c)+f_1(c+h)f_2(c)-f_1(c)f_2(c)}{h}

\displaystyle =\lim_{h\to 0}\left(f_1(c+h)\frac{f_2(c+h)-f_2(c)}{h}-\frac{f_1(c+h)-f_1(c)}{h}f_2(c)\right)

\displaystyle =\lim_{h\to 0}\left(f_1(c+h)\right)\lim_{h\to 0}\left(\frac{f_2(c+h)-f_2(c)}{h}\right)-\lim_{h\to 0}\left(\frac{f_1(c+h)-f_1(c)}{h}\right)f_2(c)

\displaystyle =f_1(c)\lim_{h\to 0}\left(\frac{f_2(c+h)-f_2(c)}{h}\right)-\lim_{h\to 0}\left(\frac{f_1(c+h)-f_1(c)}{h}\right)f_2(c)

=f_1(c)f^\prime_2(c)+f_1^\prime(c)f_2(c).

The penultimate equality follows from the continuity of f_1 at c, and the final inequality follows from the differentiability of f_1 and f_2  at c. Thus P(2) holds.

Inductive step. Suppose P(k) holds for some integer k\ge 2. Let f_1, f_2,\ldots, f_{k+1} be functions that are differentiable at some point c. Then (f_1 f_2\cdots f_{k+1})^\prime(c)=((f_1 f_2\cdots f_k)\cdot (f_{k+1}))^\prime(c). By the base case, this equals (f_1f_2\cdots f_k)^\prime(c)f_{k+1}(c)+(f_1f_2\cdots f_k)(c)f_{k+1}^\prime(c). By the inductive assumption, this equals

\displaystyle\left(\sum_{i=1}^k f_1(c)f_2(c)\cdots f_i^\prime(c)\cdots f_k(c)\right)f_{k+1}(c)+f_1(c)f_2(c)\cdots f_k(c)f_{k+1}^\prime(c)=\sum_{i=1}^{k+1} f_1(c)f_2(c)\cdots f_i^\prime(c)\cdots f_{k+1}(c).

Thus, P(k+1) holds.

It follows that P(n) holds for all n\ge 2.#

If you have another example—especially one that would be suitable for into-to-proof students (who don’t have an extensive math background)—post them in the comments.

2 Comments Add yours

  1. erikrtou says:

    You could do much the same thing for DeMorgan’s law (either the set-theoretic or propositional logic versions). Assuming the base case is at n=2.

    1. Good point. That would fit within the subject matter better than the calculus theorem. (On the flip side, the base case wouldn’t be quite as messy/deep as the base case is here).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s