Course contentsShow
← Mathematics
Lesson 2508 of 3,12150. Discrete Math — Logic and ProofFree lesson

Induction Starting at Arbitrary Indices

Proving statements for n ≥ k where k is not necessarily 0 or 1, adjusting the base case accordingly.

Induction Starting at Arbitrary Indices

What You'll Learn

You'll learn how to use mathematical induction to prove statements that only hold for integers starting at some specific value k (like n ≥ 5), rather than beginning at 0 or 1.

The Core Idea

Not every mathematical statement is true for all natural numbers—some only become true once n is large enough. For example, maybe you need to prove that 2ⁿ > n² for all n ≥ 5. Starting your induction at n = 1 would fail because 2¹ = 2 is not greater than 1² = 1, and even 2⁴ = 16 equals 4² = 16.

The solution: adjust where your induction starts.

How It Works

The structure remains the same as standard induction, but with a shifted foundation:

  1. Base Case: Prove the statement is true for n = k (your chosen starting point), not n = 0 or n = 1
  2. Inductive Hypothesis: Assume the statement holds for some arbitrary n ≥ k
  3. Inductive Step: Prove it holds for n + 1, using your assumption
  4. Conclusion: By induction, the statement is true for all integers n ≥ k

Analogy

Think of climbing a ladder that doesn't reach the ground—it starts on the 5th floor. You still prove you can step from any rung to the next (inductive step), but first you must prove you can reach that 5th-floor starting rung (base case at n = 5).

Why This Matters

Many real-world mathematical statements have thresholds. Growth rates, inequalities comparing functions, and combinatorial identities often only "kick in" after a certain point. This technique lets you prove exactly what's true, where it's true.

Key Takeaway: When proving statements for n ≥ k where k ≠ 0 or 1, simply shift your base case to n = k and proceed with standard induction structure—the logic remains identical, just anchored at a different starting point.