What is Proof by Induction?

Ever wondered how mathematicians prove something works for every single natural number without checking each one individually? That's exactly what proof by induction does for you.

The domino analogy is spot on here - if you can prove the first domino falls and that any falling domino will knock over the next one, you've proven all dominoes will fall. This structured approach lets you tackle problems that would be impossible to solve by testing every number.

💡 Key Insight: Induction is like a mathematical shortcut that saves you from infinite checking while still giving you absolute certainty about your answer.

The Principle Behind Mathematical Induction

To prove a statement P(n) is true for all natural numbers, you need three essential components that work together like puzzle pieces.

First, you've got your proposition P(n) - this is simply the statement you're trying to prove. Then comes the base case $usually n=1$, where you show the statement works for the very first value. Think of this as knocking over that crucial first domino.

Next is the inductive hypothesis - here you assume the statement is true for some arbitrary number k. You're not proving it for k, just assuming it works. Finally, the inductive step is where the magic happens - you prove that if the statement works for k, it must also work for k+1.

💡 Remember: The inductive step is usually the trickiest part, but it's where you'll gain the most marks in exams!

Step-by-Step Method for Exam Success

Here's your foolproof structure that you must follow exactly in exams - no shortcuts allowed if you want full marks.

Step 1: State your proposition clearly, labelling it P(n). Step 2: Base case - test for the smallest value $usually n=1$, show LHS equals RHS, then conclude it's true for n=1. Step 3: Inductive hypothesis - assume the proposition is true for n=k and write it out with k replacing n.

Step 4: Inductive step - state what you need to prove $the k+1 case$, start with the LHS of P$k+1$, and use algebra to manipulate it. Crucially, you must use your inductive hypothesis - this is the key link that makes everything work.

Step 5: Conclusion - write that final summary statement mentioning all parts. A solid conclusion is: "Since the proposition is true for n=1, and assuming it's true for n=k implies it's true for n=k+1, then by the principle of mathematical induction, the proposition is true for all n∈ℕ, n≥1."

💡 Exam Tip: The conclusion statement is basically a formula - just learn it and adapt it to your specific problem!

Worked Example: Sum of Integers

Let's prove that 1+2+3+...+n = n$n+1$/2 using our step-by-step method - this is a classic that often appears in exams.

Base case $n=1$: LHS = 1, RHS = 1(1+1)/2 = 1. Since LHS = RHS, P(1) is true. Inductive hypothesis: Assume P(k) is true, so 1+2+3+...+k = k$k+1$/2.

Inductive step: We need to prove 1+2+3+...+k+$k+1$ = $k+1$$k+2$/2. Starting with the LHS: $1+2+3+...+k$+$k+1$. Now here's the crucial bit - substitute using our inductive hypothesis: k$k+1$/2 + $k+1$.

Finding a common denominator: k$k+1$/2 + 2$k+1$/2 = $k(k+1)+2(k+1)$/2. Factor out $k+1$: $k+1$$k+2$/2, which is exactly our target RHS.

💡 Success Strategy: The key moment is when you substitute using your inductive hypothesis - this is where you link everything together!

Divisibility Proofs Made Simple

Divisibility problems have a special trick that makes them much easier once you know the secret approach.

For proving 7ⁿ - 1 is divisible by 6, start with your base case: when n=1, 7¹-1=6, which is clearly divisible by 6. For your inductive hypothesis, assume 7ᵏ-1 is divisible by 6, which means 7ᵏ-1 = 6m for some integer m. Rearrange this to get 7ᵏ = 6m + 1 - this rearrangement is absolutely crucial.

For the inductive step, consider 7^$k+1$ - 1 = 7×7ᵏ - 1. Substitute 7ᵏ = 6m + 1: this gives you 7$6m + 1$ - 1 = 42m + 7 - 1 = 42m + 6 = 6$7m + 1$. Since $7m + 1$ is an integer, you've proven 7^$k+1$ - 1 is divisible by 6.

💡 Divisibility Secret: Always rearrange your inductive hypothesis to make the highest power term the subject - this sets you up perfectly for the substitution step!

Inequality Proofs and Advanced Techniques

Inequality proofs are the trickiest type, but they're totally manageable when you break them down systematically.

For proving 2ⁿ > n² for n≥5, notice the base case isn't n=1 - it's n=5 because the statement isn't true for smaller values. When n=5: 2⁵ = 32 and 5² = 25, so 32 > 25 ✓. Your inductive hypothesis assumes 2ᵏ > k² for some k≥5.

The tricky bit is the inductive step. You need to prove 2^$k+1$ > $k+1$². Start with 2^$k+1$ = 2×2ᵏ. Using your hypothesis: 2×2ᵏ > 2×k² = 2k². Now you need to show that 2k² > $k+1$² for k≥5.

Expanding: 2k² > k² + 2k + 1, which simplifies to k² - 2k - 1 > 0. Using the quadratic formula, this inequality holds when k > 1 + √2 ≈ 2.41. Since k≥5, you're safely in the range where this works.

💡 Inequality Insight: Don't just assume intermediate inequalities are true - you need to prove them using techniques like the quadratic formula!

Common Mistakes and Exam Success Tips

Avoiding these common pitfalls will save you precious marks and boost your confidence in exams.

The conclusion mistake is huge - you absolutely must write the full concluding sentence mentioning the base case, inductive step, and principle of induction. It's literally free marks if you remember it. Algebraic errors in the inductive step are mark-killers, so double-check your bracket expansions and factoring.

Forgetting to use your assumption defeats the entire purpose - if you prove the n=k+1 case without using your n=k assumption, you've missed the point completely. For divisibility proofs, always rearrange your assumption to isolate the highest power term.

Your exam formula for success: State P(n) → Prove base case → Assume for n=k → Prove for n=k+1 using your assumption → Write the conclusion. Master this structure and you'll tackle any induction problem with confidence.

💡 Final Tip: Practice the conclusion statement until it's automatic - "Since the proposition is true for [base case], and assuming it's true for n=k implies it's true for n=k+1, then by the principle of mathematical induction, the proposition is true for all [relevant values of n]."