Mathematical Induction

# CHAPTER 12

Mathematical Induction #

1. Introduction #

In Chapter 11, we introduced Gauss's formula for summing integers: $n(n+1)/2$. We stated that this shortcut formula magically works for any integer $N$. But in theoretical computer science, you cannot just blindly trust a formula. You must mathematically *prove* it is unbreakable. If you want to prove the formula works for $N=5$, you can calculate it manually. But how do you prove it works for every single number up to infinity? You cannot test infinity. To solve this, we deploy Mathematical Induction. Induction is the ultimate "Domino Effect" proof. It is the mathematical foundation of Recursive Algorithms and algorithmic Loop Invariants.

2. Learning Objectives #

By the end of this chapter, you will be able to:

• Define the two-step architecture of Mathematical Induction.

• Execute a formal proof utilizing a Base Case and an Inductive Step.

• Map the logical behavior of Induction directly to the physical physics of falling dominos.

• Differentiate standard Induction from Strong Induction.

3. The Domino Analogy #

Imagine an infinitely long, straight line of standing dominos. You want to mathematically guarantee that every single domino in the infinite sequence will fall. You only have to prove two isolated facts:

1. 1. The First Domino Falls: You personally push over the very first domino in the line.

1. 2. The Knockover Rule: You prove that the physical spacing between the dominos is perfect. If *any* random domino falls, it is mathematically guaranteed to hit the one immediately next to it.

If you prove those two things, logic dictates that the first knocks over the second, the second knocks over the third, and the chain reaction securely ripples out to absolute infinity!

4. The Two Steps of Induction #

A formal Inductive Proof mirrors the domino analogy perfectly. We are trying to prove a Proposition $P(n)$ is true for all positive integers.

Step 1: The Base Case (Pushing the first domino)

• Prove that the statement works for the absolute lowest possible integer (usually $n = 1$).

• *Action:* Physically plug $1$ into the formula and verify it matches reality.

Step 2: The Inductive Step (The Knockover Rule)

• We assume the formula magically works for some random, arbitrary integer $k$. This assumption is called the Inductive Hypothesis. (Assume $P(k)$ is True).

• *Action:* Using the assumption that $k$ works, we must algebraically prove that the *very next integer* ($k+1$) also perfectly resolves. (Prove $P(k+1)$ is True).

5. Executing a Formal Proof #

Let's mathematically prove Gauss's Formula: $\sum{i=1}^{n} i = \frac{n(n+1)}{2}$.

Step 1: Base Case ($n = 1$)

• Left Side: The sum of numbers from 1 to 1 is exactly $1$.

• Right Side Formula: $\frac{1(1+1)}{2} = \frac{2}{2} = 1$.

• Both sides equal $1$. The Base Case is absolutely verified.

Step 2: Inductive Step

• *Assume $n = k$ works:* We assume $\sum{i=1}^{k} i = \frac{k(k+1)}{2}$ is a mathematically true fact.

• *Prove $n = k+1$ works:* We must show that $\sum{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}$.

*Algebraic Execution:* The sum of $k+1$ items is simply the sum of $k$ items, plus the very last item. $= \left( \sum{i=1}^{k} i \right) + (k+1)$

Substitute our assumption from above: $= \left[ \frac{k(k+1)}{2} \right] + (k+1)$

Find a common denominator to add them: $= \frac{k(k+1)}{2} + \frac{2(k+1)}{2}$ $= \frac{k(k+1) + 2(k+1)}{2}$

Factor out the common $(k+1)$: $= \frac{(k+1)(k+2)}{2}$

Conclusion: The algebra perfectly yielded the target $P(k+1)$ formula! Because the Base Case fired, and the Inductive chain is unbroken, the formula is definitively proven to infinity.

6. Strong Induction #

Standard Induction assumes $k$ works, to prove $k+1$. Strong Induction assumes that *every single integer* from $1$ all the way up to $k$ works, to prove $k+1$. This heavier assumption is required when resolving massive recursive algorithms (like proving properties of Binary Trees or Dynamic Programming arrays) where a step relies on multiple historical layers, not just the immediately preceding step.

7. Common Mistakes #

• Skipping the Base Case: If you mathematically prove the Inductive Step ($k \rightarrow k+1$), but you forget the Base Case... you proved that the dominos are spaced correctly, but you forgot to push the first one! The chain reaction never starts. The entire proof is legally invalid.

8. Exercises #

1. 1. Define the exact Base Case requirement to prove the formula: $P(n) = n! > 2^n$ (Assume Domain $n \ge 4$).

1. 2. Explain physically why assuming $P(k)$ is True in the Inductive Step is not "cheating", but rather establishing a conditional logical implication ($P(k) \rightarrow P(k+1)$).

9. MCQs with Answers #

Q10. True or False: Mathematical Induction relies on circular logic, because assuming $P(k)$ is True in order to prove $P(k+1)$ is True is mathematically cheating. a) True. This is considered a known paradox in Discrete Math. b) False. We are NOT proving $P(k)$ is true. We are proving the Conditional Statement $P(k) \rightarrow P(k+1)$. We are proving that *IF* $K$ works, *THEN* $K+1$ works. This conditional bridge, combined with the hard reality of the Base Case, creates an irrefutable cascading chain. Answer: b) False. We are NOT proving $P(k)$ is true. We are proving the Conditional Statement $P(k) \rightarrow P(k+1)$...

11. Interview Preparation #

Top Interview Questions:

• *Algorithmic Proofs:* "An interviewer asks: How can you definitively prove that a Binary Tree with $N$ leaves has exactly $N-1$ internal nodes?" *(Answer: Do not try to draw massive trees! Use Strong Induction! Prove the Base Case for 1 leaf (0 internal nodes). Assume the rule holds for any tree up to $K$ leaves. Break a $K+1$ leaf tree into two smaller sub-trees, apply the assumption, and algebraically sum the nodes to prove the theorem!)*

12. Summary #

Mathematical Induction is the highest tier of Discrete logical proofs. It grants computer scientists the god-like ability to mathematically tame absolute infinity. By mastering the sequence of anchoring a Base Case and bridging the Inductive Step, developers acquire the vocabulary necessary to verify Recursive logic paths and unbreakable server Loop Invariants.

13. Next Chapter Recommendation #

We have used Induction to prove sequences work. But what if a sequence defines itself using its own past data? What if to calculate $N$, you must first calculate $N-1$? In Chapter 13: Recursive Definitions and Recurrence Relations, we will explore the terrifying mathematics of algorithms that invoke themselves.