Skip to main content

MA 415G course notes

Benjamin Braun

Section 2.8 Induction: Part 1

Several times in this course we have used a proof technique where we checked simple cases and then showed how we could systematically "build up" our argument by using previous steps we had verified to prove that later steps hold. This technique is called proof by induction.
🔗
There are various flavors of induction, including the "method of descent", "strong induction", "weak induction", etc. We will continue to discuss various aspects of these distinctions, but what is more important than learning names is to learn and understand the key idea of induction:
verify small cases, then use those small cases to verify the next case, then use that new case to verify the next case, then use that new case to verify the next case, and then carefully explain why you can always continue this process for a specific problem or proof.
🔗
🔗
🔗
Let’s work through some examples.
🔗

Checkpoint 2.8.1.

Consider the following sequence:
\begin{equation*} \sqrt{2}, \sqrt{2+\sqrt{2}}, \sqrt{2+\sqrt{2+\sqrt{2}}}, \sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2}}}},\ldots \, . \end{equation*}
The values of this sequence are:
What do you think an upper bound for this sequence is? Why do you think this upper bound holds? How would you go about showing that this upper bound holds?
🔗
🔗

Checkpoint 2.8.2.

Compute the values of \(1+3+5+7+\cdots +(2k-1)\) for \(k=1,2,3,4,5,6\text{.}\) What do you think the value of the \(k\)-th term of this sequence is? Why do you think your answer is correct? How would you go about proving that your answer is always correct, even when \(k\) is a positive integer beyond the scope of human comprehension?
🔗
🔗

Checkpoint 2.8.3.

Consider any map formed by drawing \(n\) straight lines in the plane, each line extending infinitely in both directions, to represent the boundaries of the regions. Some regions will be compact and bounded, others will be unbounded and go off to infinity. Is it always possible to color the regions using only two colors, say white and gray, in such a way that white and gray regions never share an edge? In other words, the edges between regions always have white on one side and gray on the other side. If yes, why? If no, why not?
🔗
🔗
These three checkpoint exercises demonstrate how you can use a small number of initial data points to make a conjecture, then look at how the structure of the problem leads you to use the same pattern of logical argument repeatedly. This "pattern of logical argument" is the inductive step of an induction argument, while the small initial data points are the base cases of the inductive argument. We are now in a position to give a precise statement of the principle of mathematical induction.
🔗

Checkpoint 2.8.5.

Discuss how the structure of the Principle of Mathematical Induction applies to each of the three checkpoint problems above.
🔗
🔗
🔗
PrevTopNext