Multiple Choice Questions on Mathematical Induction Principles of
Mathematical Induction Strong Induction Applications in Various
Mathematical Areas
Each question is followed by its correct answer and a detailed solution.
1. What is the first step in a proof by mathematical induction?
a) Inductive step
b) Base case
c) Conclusion
d) Hypothesis
Answer: b) Base case
Solution: In a proof by mathematical induction, we always start with the base case. This involves
proving that the statement is true for the initial value (usually n = 1 or n = 0).
2. Which of the following statements is proved using the base case in mathematical induction?
a) P(k) implies P(k+1)
b) P(n) is true for all n
c) P(1) or P(0) is true
d) P(k+1) is true
Answer: c) P(1) or P(0) is true
Solution: The base case in mathematical induction proves that the statement is true for the initial
value, which is typically P(1) or P(0).
3. In mathematical induction, what does the inductive step prove?
a) P(1) is true
b) P(n) is true for all n
c) If P(k) is true, then P(k+1) is true
d) P(k) is false
Answer: c) If P(k) is true, then P(k+1) is true
Solution: The inductive step in mathematical induction proves that if the statement is true for some
k, then it must also be true for k+1.
4. Which of the following is NOT a step in mathematical induction?
a) Base case
b) Inductive step
c) Conclusion
d) Contradiction
Answer: d) Contradiction
Solution: The main steps in mathematical induction are the base case, inductive step, and
conclusion. Contradiction is not a standard step in induction proofs.
5. What is the purpose of the base case in mathematical induction?
a) To prove the statement for all n
b) To start the "domino effect"
c) To prove P(k) implies P(k+1)
d) To disprove the statement
Answer: b) To start the "domino effect"
Solution: The base case in mathematical induction proves that the statement is true for the initial
value, essentially starting the "domino effect" that will be continued by the inductive step.
6. In the statement "For all n ≥ 1, 1 + 2 + 3 + ... + n = n(n+1)/2", what is the base case?
a) n = 0
b) n = 1
c) n = 2
d) n = k
Answer: b) n = 1
Solution: The base case for this statement is n = 1, as the statement is defined for all n ≥ 1. We
would verify that 1 = 1(1+1)/2, which is true.
7. What assumption is made in the inductive step of a proof by mathematical induction?
a) P(1) is true
b) P(k) is true for some arbitrary k
c) P(n) is true for all n
d) P(k+1) is true
Answer: b) P(k) is true for some arbitrary k
Solution: In the inductive step, we assume that P(k) is true for some arbitrary k. This is called the
inductive hypothesis.
8. Which of the following best describes the conclusion of a proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k+1
c) The statement is true for all n ≥ 1
d) The statement is false
Answer: c) The statement is true for all n ≥ 1
Solution: The conclusion of a proof by mathematical induction states that the given statement is
true for all n greater than or equal to the base case (usually n ≥ 1).
9. What is the key principle behind mathematical induction?
a) If a statement is true for n = 1, it's true for all n
b) If a statement is true for n = k, it's true for n = k+1
c) If a statement is true for n = 1 and the inductive step holds, it's true for all n ≥ 1
d) If a statement is true for n = k+1, it's true for n = k
Answer: c) If a statement is true for n = 1 and the inductive step holds, it's true for all n ≥ 1
Solution: The principle of mathematical induction states that if a statement is true for the base case
(usually n = 1) and the inductive step proves that P(k) implies P(k+1), then the statement is true for
all n greater than or equal to the base case.
10. Which of the following statements about mathematical induction is FALSE?
a) It can be used to prove statements about all positive integers
b) It requires a base case and an inductive step
c) It can only be used for statements about integers
d) It is based on the well-ordering principle of natural numbers
Answer: c) It can only be used for statements about integers
Solution: This statement is false. While mathematical induction is commonly used for statements
about integers, it can also be applied to other well-ordered sets, such as rational numbers with a
defined ordering.
11. In proving the formula for the sum of the first n positive integers using induction, what is the
inductive hypothesis?
a) 1 + 2 + 3 + ... + n = n(n+1)/2
b) 1 + 2 + 3 + ... + k = k(k+1)/2
c) 1 + 2 + 3 + ... + (k+1) = (k+1)(k+2)/2
d) 1 + 2 + 3 + ... + n = n^2
Answer: b) 1 + 2 + 3 + ... + k = k(k+1)/2
Solution: The inductive hypothesis assumes that the statement is true for some arbitrary k. In this
case, we assume that the sum of the first k positive integers is k(k+1)/2.
12. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
. What is the next step after assuming the inductive hypothesis in a proof by induction?
a) Conclude the proof
b) Prove the base case
c) Prove that the statement holds for k+1
d) Disprove the statement
Answer: c) Prove that the statement holds for k+1
Solution: After assuming the inductive hypothesis, the next step is to prove that the statement
holds for k+1. This is the crucial part of the inductive step.
13. Which of the following is an example of a statement that can be proved by mathematical
induction?
a) All prime numbers are odd
b) For all n ≥ 1, n^3 - n is divisible by 3
c) There are infinitely many prime numbers
d) π is an irrational number
Answer: b) For all n ≥ 1, n^3 - n is divisible by 3
Solution: This statement is well-suited for proof by induction because it makes a claim about all
positive integers greater than or equal to 1. The other statements either aren't true for all n or aren't
naturally set up for induction.
14. What is the difference between simple induction and strong induction?
a) Strong induction doesn't require a base case
b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ..., P(k)
imply P(k+1)
c) Strong induction can only be used for even numbers
d) Simple induction is used for arithmetic sequences, strong induction for geometric sequences
Answer: b) Simple induction proves P(k) implies P(k+1), while strong induction proves P(1), P(2), ...,
P(k) imply P(k+1)
Solution: In simple induction, we assume P(k) is true and prove P(k+1). In strong induction, we
assume P(1), P(2), ..., P(k) are all true and then prove P(k+1).
15. Which of the following is NOT typically proved using mathematical induction?
a) Formulas for sums of series
b) Divisibility properties
c) Inequalities
d) The existence of irrational numbers
Answer: d) The existence of irrational numbers
Solution: Mathematical induction is typically used for statements that hold for all natural numbers
or integers from a certain point onward. The existence of irrational numbers is not naturally set up as
an inductive statement and is usually proved by other methods.
16. In a proof by induction of the statement "For all n ≥ 1, 2^n > n", what would be the inductive
step?
a) Prove 2^1 > 1
b) Assume 2^k > k and prove 2^(k+1) > k+1
c) Prove 2^n > n directly
d) Assume 2^(k+1) > k+1 and prove 2^k > k
Answer: b) Assume 2^k > k and prove 2^(k+1) > k+1
Solution: In the inductive step, we assume the statement is true for k (inductive hypothesis) and
then prove it's true for k+1. So we assume 2^k > k and use this to prove 2^(k+1) > k+1.
17. What is the purpose of the well-ordering principle in relation to mathematical induction?
a) It proves the base case
b) It justifies the inductive step
c) It provides the foundation for the validity of induction
d) It is used to disprove induction
Answer: c) It provides the foundation for the validity of induction
Solution: The well-ordering principle, which states that every non-empty set of positive integers
has a least element, provides the foundational justification for why mathematical induction works.
18. In proving that "For all n ≥ 1, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6" by induction, what would be
the left side of the equation in the inductive step?
a) (k+1)^2
b) 1^2 + 2^2 + ... + k^2
c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
d) k(k+1)(2k+1)/6
Answer: c) 1^2 + 2^2 + ... + k^2 + (k+1)^2
Solution: In the inductive step, we're trying to prove the statement for k+1. So the left side of the
equation would be the sum of squares up to (k+1)^2, which is 1^2 + 2^2 + ... + k^2 + (k+1)^2.
19. Which of the following best describes the relationship between the base case and the inductive
step in a proof by induction?
a) The base case is a special case of the inductive step
b) The inductive step proves the base case
c) The base case starts the inductive process, and the inductive step continues it
d) The base case and inductive step are independent and unrelated
Answer: c) The base case starts the inductive process, and the inductive step continues it
Solution: In a proof by induction, the base case provides the starting point by proving the
statement for the initial value. The inductive step then shows that if the statement is true for any
arbitrary value, it must also be true for the next value, thus continuing the process.
20. What is the final conclusion of a successful proof by mathematical induction?
a) The statement is true for n = 1
b) The statement is true for n = k implies it's true for n = k+1
c) The statement is true for all n greater than or equal to the base case
d) The statement is true for some values of n
Answer: c) The statement is true for all n greater than or equal to the base case
Solution: If both the base case and the inductive step are successfully proved, we can conclude
that the statement is true for all n greater than or equal to the value used in the base case (usually n
≥ 1 or n ≥ 0).
21. In a proof by induction of the statement "For all n ≥ 1, n! ≥ 2^(n-1)", what would be the base
case?
a) Prove 0! ≥ 2^(-1)
b) Prove 1! ≥ 2^0
c) Prove 2! ≥ 2^1
d) Prove k! ≥ 2^(k-1)
Answer: b) Prove 1! ≥ 2^0
Solution: The base case is typically the smallest value of n for which the statement is claimed to be
true. In this case, the statement is for all n ≥ 1, so the base case would be n = 1. We would need to
prove that 1! ≥ 2^(1-1), which is 1 ≥ 1.
22. What is the main difference between mathematical induction and proof by contradiction?
a) Induction proves a statement for all natural numbers, while contradiction proves a single case
b) Induction assumes the statement is true, while contradiction assumes it's false
c) Induction uses a base case, while contradiction doesn't
d) Induction is only used for equalities, while contradiction is used for inequalities
Answer: b) Induction assumes the statement is true, while contradiction assumes it's false
Solution: In mathematical induction, we assume the statement is true for some k and prove it for
k+1. In proof by contradiction, we assume the statement we want to prove is false and then derive a
contradiction.
23. Which of the following statements about strong induction is TRUE?
a) It doesn't require a base case
b) It's less powerful than simple induction
c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
d) It can only be used for even numbers
Answer: c) It assumes P(1), P(2), ..., P(k) to prove P(k+1)
Solution: Strong induction, also known as complete induction, assumes that the statement is true
for all values up to k (i.e., P(1), P(2), ..., P(k)) to prove P(k+1). This is in contrast to simple induction,
which only assumes P(k) to prove P(k+1).
24. In a proof by induction, what do we call the assumption that P(k) is true?
a) Base case
b) Inductive hypothesis
c) Conclusion
d) Axiom
Answer: b) Inductive hypothesis
Solution: In the inductive step of a proof by mathematical induction, we assume that the
statement P(k) is true for some arbitrary k. This assumption is called the inductive hypothesis.
25. Which of the following is an example of a property that is often proved using strong induction
rather than simple induction?
a) Formulas for the sum of the first n integers
b) Divisibility properties of numbers
c) The well-ordering principle
d) The fact that every integer greater than 1 is a product of primes
Answer: d) The fact that every integer greater than 1 is a product of primes
Solution: The prime factorization theorem (every integer greater than 1 is a product of primes) is
typically proved using strong induction. This is because to prove it for k+1, we might need to use the
fact that it's true for all numbers less than k+1, not just for k.
26. What is the key difference between the inductive step in simple induction and strong induction?
a)
