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

erikrtou says:

November 7, 2018 at 4:19 pm

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. Dave Richeson says:
  
  November 7, 2018 at 4:28 pm
  
  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).

Comments are closed.

Share this:

Like this:

Related

2 Comments