Inductive Proof Quiz: Practice Mathematical Induction Basics

1) Mathematical induction is primarily designed to prove statements about which set of numbers?

All real numbers

The natural numbers (1,2,3,...)

All complex numbers

All rational numbers

Induction uses a base case and a step from n = k to n = k+1, mirroring how the natural numbers progress. This makes it ideal for propositions indexed by n ∈ ℕ.

Explanation

Induction uses a base case and a step from n = k to n = k+1, mirroring how the natural numbers progress. This makes it ideal for propositions indexed by n ∈ ℕ.

2) What is the first required part of any proof by (weak) induction?

The inductive step

The base case

The conclusion

The inductive hypothesis

You must first show that the statement holds for the initial value (such as n = 0 or n = 1). This anchors the entire chain of implications used in the inductive step.

Explanation

You must first show that the statement holds for the initial value (such as n = 0 or n = 1). This anchors the entire chain of implications used in the inductive step.

3) In the inductive step, what do you assume to be true in order to prove P(k+1)?

P(1) only

P(k+1) itself

P(k) for some integer k

The statement is false

The inductive hypothesis assumes that P(k) holds for an arbitrary integer k. From this assumption you derive that P(k+1) must also be true.

Explanation

The inductive hypothesis assumes that P(k) holds for an arbitrary integer k. From this assumption you derive that P(k+1) must also be true.

4) What is the logical form captured by the inductive step in a standard induction proof?

P(k+1) → P(k)

P(1) → P(2) only

P(k) → P(1)

P(k) → P(k+1)

The inductive step must show that whenever the statement is true at k, it is also true at k+1. This implication, combined with the base case, covers all higher n.

Explanation

The inductive step must show that whenever the statement is true at k, it is also true at k+1. This implication, combined with the base case, covers all higher n.

5) Which two parts must every induction proof have to be valid?

An assumption and a conclusion

A hypothesis and an antithesis

A base case and an inductive step

A premise and a contradiction

You must verify the statement for the starting value (base case) and then prove that P(k) implies P(k+1) (inductive step). Both components are essential for the "domino effect."

Explanation

You must verify the statement for the starting value (base case) and then prove that P(k) implies P(k+1) (inductive step). Both components are essential for the "domino effect."

6) To prove n! > 2^n for all integers n ≥ 4, which is the appropriate base case?

Check that 1! > 2^1

Check that 0! > 2^0

Check that k! > 2^k for general k

Check that 4! > 2^4

The claim begins at n = 4, so the first value you must check is n = 4. Verifying 4! > 2^4 provides the starting point for the inductive argument.

Explanation

The claim begins at n = 4, so the first value you must check is n = 4. Verifying 4! > 2^4 provides the starting point for the inductive argument.

7) To prove that a set with n elements has 2^n subsets, which statement is P(k+1) in the induction?

A set with k elements has 2^k subsets

A set with n elements has 2^n subsets

A set with 1 element has 2^1 subsets

A set with k+1 elements has 2^{k+1} subsets

In the inductive step you assume P(k): a k-element set has 2^k subsets, and aim to show P(k+1): any (k+1)-element set has exactly 2^{k+1} subsets.

Explanation

In the inductive step you assume P(k): a k-element set has 2^k subsets, and aim to show P(k+1): any (k+1)-element set has exactly 2^{k+1} subsets.

8) For the formula 1 + 2 + … + n = n(n+1)/2, what is the statement P(k) used in an induction proof?

1 + 2 + … + n = n(n+1)/2

1 + 2 + … + (k+1) = (k+1)(k+2)/2

1 = 1·2/2

1 + 2 + … + k = k(k+1)/2

P(k) asserts that the sum of the first k integers equals k(k+1)/2. This is the crucial inductive hypothesis used to derive the case for k+1.

Explanation

P(k) asserts that the sum of the first k integers equals k(k+1)/2. This is the crucial inductive hypothesis used to derive the case for k+1.

9) When proving 1 + 2 + … + n = n(n+1)/2, what is the goal in the inductive step P(k+1)?

1 + 2 + … + k = k(k+1)/2

K+1 = k+1

The formula works for n = 1

1 + 2 + … + k + (k+1) = (k+1)(k+2)/2

Starting from P(k), you add (k+1) to both sides and simplify. The goal is to obtain exactly 1 + … + k + (k+1) = (k+1)(k+2)/2.

Explanation

Starting from P(k), you add (k+1) to both sides and simplify. The goal is to obtain exactly 1 + … + k + (k+1) = (k+1)(k+2)/2.

10) To prove 3^n − 1 is divisible by 2 for all n ≥ 1, which base case should you verify?

3^2 − 1 is divisible by 2

3^0 − 1 is divisible by 2

3^k − 1 is divisible by 2

3^1 − 1 is divisible by 2

Because the statement is claimed for n ≥ 1, you start with n = 1. Checking 3^1 − 1 = 2 confirms the property holds at the base level.

Explanation

Because the statement is claimed for n ≥ 1, you start with n = 1. Checking 3^1 − 1 = 2 confirms the property holds at the base level.

11) In an inductive proof that 3^n − 1 is divisible by 2, after assuming 3^k − 1 = 2m, what is the natural next step?

Re-prove the base case

Assume 3^{k+1} − 1 is divisible by 2 without justification

Conclude the proof is complete

Rewrite 3^{k+1} as 3·3^k and examine 3^{k+1} − 1

You express 3^{k+1} as 3·3^k, substitute the inductive hypothesis for 3^k, and factor the result. This shows 3^{k+1} − 1 can also be written as 2 times an integer.

Explanation

You express 3^{k+1} as 3·3^k, substitute the inductive hypothesis for 3^k, and factor the result. This shows 3^{k+1} − 1 can also be written as 2 times an integer.

12) How does strong induction differ from standard (weak) induction?

It leads to a weaker conclusion

It uses a different type of base case

The inductive hypothesis assumes P(1), P(2), …, P(k) are all true

It does not require an inductive step

In strong induction you may use all previously established cases up to k to prove P(k+1). This richer assumption is often helpful for recursive or number-theoretic arguments.

Explanation

In strong induction you may use all previously established cases up to k to prove P(k+1). This richer assumption is often helpful for recursive or number-theoretic arguments.

13) What is the inductive hypothesis in a strong induction proof up to k?

Assume only P(k) is true

Assume P(k+1) is true

Assume P(k−1) is true

Assume P(1), P(2), …, P(k) are all true

Instead of assuming just P(k), strong induction assumes the statement holds for every integer from the base case through k. You then use this collection of facts to deduce P(k+1).

Explanation

Instead of assuming just P(k), strong induction assumes the statement holds for every integer from the base case through k. You then use this collection of facts to deduce P(k+1).

14) To prove that any postage amount ≥ 12 can be formed using 4- and 5-cent stamps, which is a suitable set of base cases?

Verify only P(12)

Verify P(1), P(2), P(3), and P(4)

Verify P(4) and P(5) only

Verify P(12), P(13), P(14), and P(15)

For such coin/postage problems, you often need several consecutive base cases so that subtracting 4 or 5 from any larger amount lands on a previously verified value. 12–15 form a useful starting block.

Explanation

For such coin/postage problems, you often need several consecutive base cases so that subtracting 4 or 5 from any larger amount lands on a previously verified value. 12–15 form a useful starting block.

15) A student proves P(1) and P(3), and then shows that P(k) → P(k+2). What have they established?

P(n) holds for all integers n ≥ 1

P(n) holds for all even integers n ≥ 2

Nothing meaningful has been proven

P(n) holds for all odd integers n ≥ 1

From P(1) and the step k → k+2, you get P(1), P(3), P(5), …; from P(3) you get P(3), P(5), P(7), …. Together these cover all odd n ≥ 1, but not even n.

Explanation

From P(1) and the step k → k+2, you get P(1), P(3), P(5), …; from P(3) you get P(3), P(5), P(7), …. Together these cover all odd n ≥ 1, but not even n.

16) Which statement about the base case in induction is correct?

The base case must always be n = 1

The base case must always be n = 0

The base case is optional if P(k) → P(k+1) is proven

If your theorem asserts P(n) for all n ≥ N, then the base case is n = N. It could be 0, 1, 4, or any other starting index specified in the statement.

Explanation

If your theorem asserts P(n) for all n ≥ N, then the base case is n = N. It could be 0, 1, 4, or any other starting index specified in the statement.

17) Induction is considered a form of which broader type of reasoning?

Abductive reasoning

Informal inductive reasoning (as in statistics)

Deductive reasoning

Analogical reasoning

Despite its name, mathematical induction is fully deductive: from axioms and the proven implication P(k)→P(k+1), we logically conclude that P(n) holds for all relevant n.

Explanation

Despite its name, mathematical induction is fully deductive: from axioms and the proven implication P(k)→P(k+1), we logically conclude that P(n) holds for all relevant n.

18) Why is induction accepted as a valid proof technique in arithmetic?

It is based only on numerical examples

It applies only to finite sets

It is equivalent to the Well-Ordering Principle for the natural numbers

It is an axiom of Euclidean geometry

The Induction Axiom and the Well-Ordering Principle (every nonempty subset of ℕ has a least element) can each be derived from the other, so either one justifies induction.

Explanation

The Induction Axiom and the Well-Ordering Principle (every nonempty subset of ℕ has a least element) can each be derived from the other, so either one justifies induction.

19) Any proof done with weak induction can also be carried out with strong induction.

True

False

Strong induction assumes all P(1)…P(k) at once, so it includes the weaker assumption P(k). This means any argument that works with weak induction can be replicated using strong induction.

Explanation

Strong induction assumes all P(1)…P(k) at once, so it includes the weaker assumption P(k). This means any argument that works with weak induction can be replicated using strong induction.

20) If you have a correct base case and have shown P(k) → P(k+1) for all k beyond the base, what can you conclude?

P(n) holds for exactly one value of n

P(n) holds for all integers n greater than or equal to the base case

P(n) holds only for n = base and n = base + 1

P(n) holds for infinitely many n, but not necessarily all

The base case guarantees the first 'domino' falls, and the implication P(k)→P(k+1) makes every subsequent case follow. Thus P(n) is true for all n ≥ base.

Explanation

The base case guarantees the first 'domino' falls, and the implication P(k)→P(k+1) makes every subsequent case follow. Thus P(n) is true for all n ≥ base.