Solved Exercises on Mathematical Induction Basics in Grade 8

Master mathematical induction: base case, inductive hypothesis, and inductive step through these 5 detailed exercises.

Solution: Exercises 1 to 3
1 Base case demonstration
Exercise 1
Prove by mathematical induction that for all positive integers n:
\(1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}\)
Definition:

Mathematical Induction: A proof technique to establish statements for all natural numbers using two steps: base case and inductive step

Base Case: Verify the statement for the smallest value (usually n = 1)

Inductive Hypothesis: Assume the statement is true for n = k

Inductive Step: Prove the statement for n = k+1 using the inductive hypothesis

Induction method:
  1. Base Case: Verify for n = 1
  2. Inductive Hypothesis: Assume true for n = k
  3. Inductive Step: Prove for n = k+1
  4. Conclusion: State the result holds for all n ≥ 1
Base Case
\(n = 1\)
Left Side
\(1\)
Right Side
\(\frac{1(1+1)}{2} = 1\)
Step 1: Base Case (n = 1)

Left side: \(1\)

Right side: \(\frac{1(1+1)}{2} = \frac{2}{2} = 1\)

✓ Both sides equal 1

Step 2: Inductive Hypothesis

Assume that for some positive integer k: \(1 + 2 + 3 + ... + k = \frac{k(k+1)}{2}\)

Step 3: Inductive Step

We need to prove: \(1 + 2 + 3 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}\)

Step 4: Using the inductive hypothesis

\(1 + 2 + 3 + ... + k + (k+1) = \frac{k(k+1)}{2} + (k+1)\)

\(= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1) + 2(k+1)}{2}\)

\(= \frac{(k+1)(k + 2)}{2}\)

\(1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}\) for all positive integers n
Final answer:

By mathematical induction, the formula \(1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}\) holds for all positive integers n

Applied rules:

• Base Case Verification: Essential starting point of induction

• Inductive Hypothesis: Assume statement is true for n = k

• Algebraic Manipulation: Factor out common terms to reach desired form

2 Power of 2 proof
Exercise 2
Prove by mathematical induction that for all positive integers n:
\(2^1 + 2^2 + 2^3 + ... + 2^n = 2^{n+1} - 2\)
Definition:

Geometric series sum: The sum of powers of 2 follows a specific pattern

Base Case
\(n = 1\)
Left Side
\(2^1 = 2\)
Right Side
\(2^{1+1} - 2 = 4 - 2 = 2\)
Step 1: Base Case (n = 1)

Left side: \(2^1 = 2\)

Right side: \(2^{1+1} - 2 = 2^2 - 2 = 4 - 2 = 2\)

✓ Both sides equal 2

Step 2: Inductive Hypothesis

Assume that for some positive integer k: \(2^1 + 2^2 + ... + 2^k = 2^{k+1} - 2\)

Step 3: Inductive Step

We need to prove: \(2^1 + 2^2 + ... + 2^k + 2^{k+1} = 2^{k+2} - 2\)

Step 4: Using the inductive hypothesis

\(2^1 + 2^2 + ... + 2^k + 2^{k+1} = (2^{k+1} - 2) + 2^{k+1}\)

\(= 2 \cdot 2^{k+1} - 2 = 2^{k+2} - 2\)

Step 5: Verification

Both sides match: \(2^{k+2} - 2 = 2^{k+2} - 2\)

\(2^1 + 2^2 + ... + 2^n = 2^{n+1} - 2\) for all positive integers n
Final answer:

By mathematical induction, the formula holds for all positive integers n

Applied rules:

• Power Properties: \(2^a + 2^a = 2 \cdot 2^a = 2^{a+1}\)

• Inductive Hypothesis: Substitute the assumed truth

• Verification: Check that both sides match after algebraic manipulation

3 Inequality proof
Exercise 3
Prove by mathematical induction that for all integers n ≥ 4:
\(2^n > n^2\)
Definition:

Exponential vs polynomial growth: Exponential functions eventually exceed polynomial functions

Base Case
\(n = 4\)
Left Side
\(2^4 = 16\)
Right Side
\(4^2 = 16\)
Step 1: Base Case (n = 4)

Left side: \(2^4 = 16\)

Right side: \(4^2 = 16\)

Since \(16 > 16\) is false, we check the next value: \(2^5 = 32 > 5^2 = 25\) ✓

We'll prove for n ≥ 5, but the statement holds for n ≥ 4

Step 2: Base Case Verification

For n = 5: \(2^5 = 32\) and \(5^2 = 25\), so \(32 > 25\) ✓

Step 3: Inductive Hypothesis

Assume that for some integer k ≥ 5: \(2^k > k^2\)

Step 4: Inductive Step

We need to prove: \(2^{k+1} > (k+1)^2\)

Step 5: Using the inductive hypothesis

\(2^{k+1} = 2 \cdot 2^k > 2k^2\) (by inductive hypothesis)

We need to show: \(2k^2 > (k+1)^2\)

This is equivalent to: \(2k^2 > k^2 + 2k + 1\)

Which simplifies to: \(k^2 > 2k + 1\)

For k ≥ 5: \(k^2 - 2k - 1 = k(k-2) - 1 ≥ 5(3) - 1 = 14 > 0\)

Therefore: \(2^{k+1} > (k+1)^2\)

\(2^n > n^2\) for all integers n ≥ 5
Final answer:

By mathematical induction, \(2^n > n^2\) for all integers n ≥ 5

Applied rules:

• Inequality Manipulation: Preserve direction when multiplying by positive numbers

• Quadratic Analysis: Determine when \(k^2 > 2k + 1\)

• Verification: Check base case carefully for inequalities

Rules and methods, laws,...
\(P(1) \land [P(k) \Rightarrow P(k+1)] \Rightarrow P(n) \text{ for all } n \geq 1\)
Mathematical Induction Principle
Base Case
\(P(1)\)
Verify for initial value
Inductive Hypothesis
\(P(k)\)
Assume true for k
Inductive Step
\(P(k) \Rightarrow P(k+1)\)
Prove for k+1
Key definitions:

Mathematical Induction: A proof technique to establish statements for all natural numbers

Base Case: The initial verification for the smallest value

Inductive Hypothesis: The assumption that the statement holds for n = k

Inductive Step: The proof that if the statement holds for n = k, then it holds for n = k+1

Complete methodology:
  1. State the proposition: Define what P(n) represents
  2. Base Case: Verify P(1) is true
  3. Inductive Hypothesis: Assume P(k) is true for some k ≥ 1
  4. Inductive Step: Prove P(k+1) using P(k)
  5. Conclusion: State that P(n) holds for all n ≥ 1
Tip 1: Always verify the base case carefully!
Tip 2: The inductive hypothesis is an assumption, not a given fact.
Tip 3: Look for ways to use the inductive hypothesis in your algebra.
Tip 4: For inequalities, sometimes you need to prove a stronger statement.
Common errors: Forgetting base case, misusing inductive hypothesis, algebraic mistakes, incorrect domain specification.
Exam preparation: Practice basic formulas, work on algebraic manipulation, understand when to use strong vs weak induction.
Formulas to know by heart:

• Sum of first n integers: \(1 + 2 + ... + n = \frac{n(n+1)}{2}\)

• Sum of first n squares: \(1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}\)

• Sum of powers of 2: \(2^1 + 2^2 + ... + 2^n = 2^{n+1} - 2\)

• Induction principle: Base case + inductive step = universal truth

Solution: Exercises 4 to 5
4 Sum of cubes
Exercise 4
Prove by mathematical induction that for all positive integers n:
\(1^3 + 2^3 + 3^3 + ... + n^3 = \left[\frac{n(n+1)}{2}\right]^2\)
Definition:

Sum of cubes formula: The sum of cubes equals the square of the sum of integers

Base Case
\(n = 1\)
Left Side
\(1^3 = 1\)
Right Side
\(\left[\frac{1(1+1)}{2}\right]^2 = 1^2 = 1\)
Step 1: Base Case (n = 1)

Left side: \(1^3 = 1\)

Right side: \(\left[\frac{1(1+1)}{2}\right]^2 = \left[\frac{2}{2}\right]^2 = 1^2 = 1\)

✓ Both sides equal 1

Step 2: Inductive Hypothesis

Assume that for some positive integer k: \(1^3 + 2^3 + ... + k^3 = \left[\frac{k(k+1)}{2}\right]^2\)

Step 3: Inductive Step

We need to prove: \(1^3 + 2^3 + ... + k^3 + (k+1)^3 = \left[\frac{(k+1)(k+2)}{2}\right]^2\)

Step 4: Using the inductive hypothesis

\(1^3 + 2^3 + ... + k^3 + (k+1)^3 = \left[\frac{k(k+1)}{2}\right]^2 + (k+1)^3\)

\(= \frac{k^2(k+1)^2}{4} + (k+1)^3 = \frac{k^2(k+1)^2 + 4(k+1)^3}{4}\)

\(= \frac{(k+1)^2[k^2 + 4(k+1)]}{4} = \frac{(k+1)^2[k^2 + 4k + 4]}{4}\)

\(= \frac{(k+1)^2(k+2)^2}{4} = \left[\frac{(k+1)(k+2)}{2}\right]^2\)

Step 5: Verification

Both sides match the required form

\(1^3 + 2^3 + ... + n^3 = \left[\frac{n(n+1)}{2}\right]^2\) for all positive integers n
Final answer:

By mathematical induction, the formula holds for all positive integers n

Applied rules:

• Algebraic Identity: Factoring out common terms

• Perfect Square: Recognizing \(k^2 + 4k + 4 = (k+2)^2\)

• Inductive Hypothesis: Substituting the assumed equation

5 Divisibility proof
Exercise 5
Prove by mathematical induction that for all positive integers n:
\(7^n - 1\) is divisible by 6
Definition:

Divisibility: An integer a is divisible by integer b if a = bq for some integer q

Base Case
\(n = 1\)
Expression
\(7^1 - 1 = 6\)
Divisible by 6
Yes: \(6 ÷ 6 = 1\)
Step 1: Base Case (n = 1)

\(7^1 - 1 = 7 - 1 = 6\)

Since 6 is divisible by 6, the base case holds ✓

Step 2: Inductive Hypothesis

Assume that for some positive integer k: \(7^k - 1\) is divisible by 6

This means: \(7^k - 1 = 6m\) for some integer m

Step 3: Inductive Step

We need to prove: \(7^{k+1} - 1\) is divisible by 6

Step 4: Using the inductive hypothesis

\(7^{k+1} - 1 = 7 \cdot 7^k - 1\)

\(= 7 \cdot 7^k - 7 + 7 - 1 = 7(7^k - 1) + 6\)

\(= 7(6m) + 6 = 42m + 6 = 6(7m + 1)\)

Step 5: Conclusion

Since \(7^{k+1} - 1 = 6(7m + 1)\), it is divisible by 6

\(7^n - 1\) is divisible by 6 for all positive integers n
Final answer:

By mathematical induction, \(7^n - 1\) is divisible by 6 for all positive integers n

Applied rules:

• Divisibility Definition: Express as a multiple of the divisor

• Algebraic Manipulation: Adding and subtracting the same term strategically

• Factorization: Factor out the divisor to show divisibility

Complete Course: Laws, Methods, Rules, Definitions, Expressions
\(P(1) \land \forall k \geq 1: [P(k) \Rightarrow P(k+1)] \Rightarrow \forall n \geq 1: P(n)\)
Principle of Mathematical Induction
Key definitions:

Mathematical Induction: A proof technique to establish statements for all natural numbers using two steps: base case and inductive step

Base Case: The verification that the statement holds for the smallest value (usually n = 1)

Inductive Hypothesis: The assumption that the statement is true for some arbitrary positive integer k

Inductive Step: The proof that if the statement is true for n = k, then it must also be true for n = k+1

Domino Effect: Once the base case is established and the inductive step is proven, the statement cascades to all positive integers

Complete methodology:
  1. Statement Setup: Clearly define what P(n) represents mathematically
  2. Base Case Verification: Show that P(1) is true by direct calculation
  3. Inductive Hypothesis: Assume P(k) is true for an arbitrary positive integer k
  4. Inductive Step Proof: Using the inductive hypothesis, prove that P(k+1) is true
  5. Logical Connection: Demonstrate that P(k) implies P(k+1) through algebraic manipulation
  6. Conclusion: State that by mathematical induction, P(n) is true for all positive integers n
Tip 1: Always verify the base case first - it's the foundation of the proof!
Tip 2: The inductive hypothesis is an assumption you're allowed to use in your proof.
Tip 3: In the inductive step, look for ways to substitute the inductive hypothesis.
Tip 4: For inequalities, sometimes you need to strengthen your inductive hypothesis.
Tip 5: Work backwards from your target to see what needs to be shown.
Common errors: Forgetting base case, misapplying inductive hypothesis, algebraic mistakes, assuming what you're trying to prove.
Exam preparation: Practice standard formulas (sums, powers), master algebraic manipulation, understand the logical structure of induction.
Applications: Proving formulas for sequences, verifying divisibility properties, establishing combinatorial identities.
Essential formulas to know by heart:

• Sum of first n integers: \(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\)

• Sum of first n squares: \(\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\)

• Sum of first n cubes: \(\sum_{i=1}^{n} i^3 = \left[\frac{n(n+1)}{2}\right]^2\)

• Geometric series: \(\sum_{i=0}^{n} ar^i = a\frac{r^{n+1}-1}{r-1}\) (r ≠ 1)

• Powers of 2: \(\sum_{i=1}^{n} 2^i = 2^{n+1} - 2\)

Exercise with Visualization: Induction Patterns
Exercise 6: Pattern Recognition
Compare the growth patterns of these sequences:
\(S_1(n) = 1 + 2 + ... + n = \frac{n(n+1)}{2}\) (quadratic growth)
\(S_2(n) = 1^3 + 2^3 + ... + n^3 = \left[\frac{n(n+1)}{2}\right]^2\) (quartic growth)
\(S_3(n) = 2^n - 1\) (exponential growth)

Analysis: The chart illustrates different growth rates and validates our inductive proofs.

  • \(S_1(n)\): Quadratic growth, validated by first exercise
  • \(S_2(n)\): Quartic growth (square of quadratic), validated by fourth exercise
  • \(S_3(n)\): Exponential growth, showing rapid increase

Questions & Answers

Question: I'm confused about the inductive hypothesis. Are we assuming something is true before we've proven it? Isn't that circular reasoning?

Answer: This is a common misconception! The inductive hypothesis is not circular reasoning:

  • We're not assuming the final conclusion is true for all n
  • We're only assuming P(k) is true for some specific (arbitrary) value k
  • We then use this assumption to prove P(k+1) is true
  • The logic is: IF P(k) is true, THEN P(k+1) is true

Think of it like a domino effect: We know the first domino falls (base case), and we prove that if any domino falls, the next one must fall too (inductive step). This guarantees all dominos fall.

The inductive hypothesis is just a tool to establish the connection between consecutive cases.

Question: In the divisibility proof (Exercise 5), how did you know to rewrite \(7^{k+1} - 1\) as \(7(7^k - 1) + 6\)? That seems like a clever trick.

Answer: This is a standard technique in induction proofs involving exponential expressions. Here's the thought process:

  • We want to connect \(7^{k+1}\) to \(7^k\) so we can use the inductive hypothesis
  • We rewrite \(7^{k+1} = 7 \cdot 7^k\)
  • We want to create the expression \(7^k - 1\) that appears in our hypothesis
  • So we write: \(7 \cdot 7^k - 1 = 7 \cdot 7^k - 7 + 7 - 1 = 7(7^k - 1) + 6\)

The key insight is to add and subtract the same value strategically to create the expression from the inductive hypothesis. This is a common pattern in induction proofs with exponentials.

With practice, you'll recognize when to apply this technique.

Question: Why do we need both the base case AND the inductive step? Can't we just prove the inductive step alone?

Answer: Both components are essential - think of them as a chain:

  • The base case provides the first link in the chain (the starting point)
  • The inductive step provides the mechanism to connect each link to the next
  • Without the base case, there's nothing to start the chain reaction
  • Without the inductive step, we can't extend the proof beyond the base case

Consider this analogy: If you know that if one domino falls then the next one falls (inductive step), but you don't know that the first domino falls (base case), you can't conclude that any domino falls.

Mathematical induction is like a ladder: you need the bottom rung (base case) and the knowledge that you can climb from any rung to the next (inductive step).

Question: When proving inequalities by induction, I sometimes get stuck. How do I know what to aim for in the inductive step?

Answer: When working with inequalities in induction, follow this systematic approach:

  1. Start with what you need to prove: Write down P(k+1) explicitly
  2. Use the inductive hypothesis: Substitute the known inequality for P(k)
  3. Build a bridge: Try to connect the expression from the inductive hypothesis to what you need
  4. Prove intermediate inequalities: Sometimes you need to prove auxiliary facts
  5. Chain the inequalities: Combine all steps to reach the desired conclusion

For example, in proving \(2^n > n^2\), we showed that if \(2^k > k^2\), then we needed to establish that the increment maintains the inequality. Often, proving a stronger statement helps make the inductive step work.

The key is to work backwards from your target to see what relationships you need to establish.

Question: Can mathematical induction be used to prove anything about all positive integers, or are there limitations?

Answer: Mathematical induction is powerful but has specific requirements:

Requirements for using induction:

  • The statement must be about positive integers (or integers ≥ some starting value)
  • You must be able to prove a base case
  • You must be able to establish the inductive step: P(k) ⇒ P(k+1)

Limitations:

  • Cannot be used for statements about real numbers or continuous domains
  • Doesn't work for statements that aren't naturally connected across consecutive integers
  • Some statements require more sophisticated variants (strong induction, structural induction)

Induction works best for statements that have a recursive or iterative structure, where knowing the result for k helps determine it for k+1.