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:
- Base Case: Prove the statement is true for n = k (your chosen starting point), not n = 0 or n = 1
- Inductive Hypothesis: Assume the statement holds for some arbitrary n ≥ k
- Inductive Step: Prove it holds for n + 1, using your assumption
- 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.