Course contentsShow
← Computer Science
Lesson 89 of 2,8722. Discrete Mathematics for CSFree lesson

Inductive Step: The Core Argument

Proving that if the statement holds for n=k, then it must also hold for n=k+1.

Inductive Step: The Core Argument

What You'll Learn

You'll learn how to prove that if a statement works for one case (n=k), it automatically works for the next case (n=k+1) — the crucial domino-push in mathematical induction.

The Core Idea

In the Inductive Step, you assume your statement is true for some arbitrary value n=k (this is your Inductive Hypothesis from the previous lesson), and then use that assumption to prove it must also be true for n=k+1.

Think of it like dominoes: if you can prove that whenever any domino falls (that's your assumption for k), it always knocks over the next domino (proving it for k+1), then you've shown the entire chain will fall — as long as the first domino tips (that's your Base Case).

How It Works

  1. Start with the Inductive Hypothesis: Write "Assume the statement is true for n=k"
  2. State what you need to prove: Write "We must show it's true for n=k+1"
  3. Use algebraic manipulation: Transform the k+1 case using the k case assumption
  4. Arrive at the conclusion: Show the statement holds for k+1

Example skeleton:

  • Hypothesis: Assume formula holds for n=k
  • Goal: Prove it holds for n=k+1
  • Method: Substitute k+1 into the formula, then manipulate it using your assumption about k until you show it matches the expected form

The beauty is that you don't prove it for every number individually — you prove the chain reaction. Combined with your Base Case, you've proven it for all natural numbers.

Key Takeaway: The Inductive Step proves the "if-then" connection: IF the statement is true for n=k, THEN it must be true for n=k+1, creating an unstoppable chain from your base case onward.