Questions & explanations
1. Which of the following sets does NOT satisfy the well-ordering principle?
- {…, -2, -1, 0, 1, 2}
- {2, 4, 6, 8, 10}
- {1, 2, 3, 4, 5, …}
- {1, 2, 3, 4, 5}
Answer: {…, -2, -1, 0, 1, 2}
The well-ordering principle states that every non-empty set of natural numbers has a least element. The set {…, -2, -1, 0, 1, 2} contains negative integers and zero, which are not natural numbers; moreover, it has no least element because it extends infinitely in the negative direction. Hence, it does not satisfy the well-ordering principle.
2. In the domino analogy for induction, what two conditions ensure all dominoes fall?
- First domino falls; last domino is heavy.
- First domino falls; each domino knocks the next.
- All dominoes are equally spaced; first domino is pushed.
- Dominoes are made of plastic; first domino falls.
Answer: First domino falls; each domino knocks the next.
The domino analogy requires two conditions: (1) the first domino falls (base case), and (2) if any domino falls, it knocks over the next one (inductive step). These guarantee that all dominoes fall, just as the base case and inductive step guarantee a statement is true for all natural numbers.
3. Let b₁ = 2, b₂ = 5, and bₙ₊₁ = 5bₙ − 6bₙ₋₁ for n ≥ 2. Which of the following is the correct closed form for bₙ?
- bₙ = 2ⁿ⁻¹ + 3ⁿ⁻¹
- bₙ = 2ⁿ + 3ⁿ⁻¹
- bₙ = 2ⁿ⁻¹ + 3ⁿ
- bₙ = 2ⁿ + 3ⁿ
Answer: bₙ = 2ⁿ⁻¹ + 3ⁿ⁻¹
Using strong induction, we verify base cases n=1 and n=2: b₁=2=2⁰+3⁰, b₂=5=2¹+3¹. Assume true for all m≤k. Then bₖ₊₁ = 5bₖ − 6bₖ₋₁ = 5(2ᵏ⁻¹+3ᵏ⁻¹) − 6(2ᵏ⁻²+3ᵏ⁻²) = (5·2ᵏ⁻¹−6·2ᵏ⁻²)+(5·3ᵏ⁻¹−6·3ᵏ⁻²) = 2ᵏ⁻²(10−6)+3ᵏ⁻²(15−6) = 4·2ᵏ⁻²+9·3ᵏ⁻² = 2ᵏ+3ᵏ = 2⁽ᵏ⁺¹⁾⁻¹+3⁽ᵏ⁺¹⁾⁻¹. Hence bₙ = 2ⁿ⁻¹+3ⁿ⁻¹.
4. A sequence is defined by a1 = 1, a2 = 2, and an+1 = 3an - 2an-1 for n ≥ 2. Which of the following is the correct statement about proving an = 2^(n-1) by induction?
- Strong induction is needed because the recurrence uses both ak and ak-1.
- Ordinary induction works because P(k) alone implies P(k+1).
- Ordinary induction fails because P(1) is not true.
- Strong induction fails because the base cases are insufficient.
Answer: Strong induction is needed because the recurrence uses both ak and ak-1.
The recurrence an+1 = 3an - 2an-1 depends on both an and an-1. Ordinary induction only assumes P(k) to prove P(k+1), but here we need P(k) and P(k-1). Strong induction assumes P(1) through P(k) are true, which provides both needed values. Hence strong induction is required.
5. For which n does 4^n > 3^n + n^2 hold?
- n ≥ 0
- n ≥ 1
- n ≥ 2
- n ≥ 3
Answer: n ≥ 2
Check n=0: 1>1 false; n=1: 4>4 false; n=2: 16>13 true; n=3: 64>36 true. For n≥2, inequality holds by induction: assume true for k≥2, then 4^{k+1}=4·4^k > 4·3^k+4k^2 ≥ 3^{k+1}+(k+1)^2 since 4·3^k+4k^2 - (3^{k+1}+(k+1)^2) = 3^k+3k^2-2k-1 ≥ 0 for k≥2. Thus holds for all n≥2.
6. For n ≥ 1, which value of 5^{2n+2} - 24n - 25 is divisible by 576?
- 576m - 1 for some integer m
- 576m + 1 for some integer m
- 576m for some integer m
- 576m + 24 for some integer m
Answer: 576m for some integer m
By induction: base n=1 gives 576, divisible by 576. Assume true for n=k: 5^{2k+2} - 24k - 25 = 576m. For n=k+1, using split-coefficient (25 = 1+24), we get 5^{2k+4} - 24(k+1) - 25 = 576(m + (5^{2k+2}-1)/24). Since 5^{2k+2} ≡ 1 mod 24, the expression is divisible by 576.
7. In proving cos α · cos 2α ·... · cos 2^{n-1}α = sin(2^n α)/(2^n sin α) by induction, what is the correct inductive step?
- Multiply P_k by cos 2^k α and use sin(2^k α) cos(2^k α) = (1/2) sin(2^k α)
- Multiply P_k by cos 2^k α and use sin(2^k α) cos(2^k α) = sin(2^{k+1} α)
- Multiply P_k by cos 2^k α and use sin(2^k α) cos(2^k α) = (1/2) sin(2^{k+1} α)
- Multiply P_k by cos 2^k α and use sin(2^k α) cos(2^k α) = sin(2^k α)
Answer: Multiply P_k by cos 2^k α and use sin(2^k α) cos(2^k α) = (1/2) sin(2^{k+1} α)
The inductive hypothesis gives P_k = sin(2^k α)/(2^k sin α). Multiplying by cos(2^k α) gives P_{k+1} = sin(2^k α) cos(2^k α)/(2^k sin α). Using sin(2θ) = 2 sin θ cos θ, we get sin(2^k α) cos(2^k α) = (1/2) sin(2^{k+1} α). Thus P_{k+1} = sin(2^{k+1} α)/(2^{k+1} sin α).
8. For n ∈ ℕ, let S(n) = Σ_{r=1}^n 1/(r(r+1)(r+2)). Which of the following is true?
- S(n) = n(n+1)/(4(n+2)(n+3))
- S(n) = n(n+2)/(4(n+1)(n+3))
- S(n) = n(n+3)/(4(n+1)(n+2))
- S(n) = n(n+4)/(4(n+1)(n+2))
Answer: S(n) = n(n+3)/(4(n+1)(n+2))
By induction, base case n=1 gives LHS=1/6, RHS=1·4/(4·2·3)=4/24=1/6. Assume true for n=k, then S(k+1)=S(k)+1/((k+1)(k+2)(k+3)). Substituting S(k) and simplifying yields (k+1)(k+4)/(4(k+2)(k+3)), which matches the formula for n=k+1. Hence the formula holds for all n.
9. In the induction proof of Σ_{r=1}^n 1/(r(r+1)) = n/(n+1), what is the inductive step after assuming P(k)?
- Add 1/((k+1)(k+2)) to k/(k+1) and simplify to k/(k+2)
- Add 1/((k+1)(k+2)) to k/(k+1) and simplify to (k+1)/(k+2)
- Add 1/((k+1)(k+2)) to k/(k+1) and simplify to (k+2)/(k+1)
- Add 1/((k+1)(k+2)) to k/(k+1) and simplify to (k+1)/(k+1)
Answer: Add 1/((k+1)(k+2)) to k/(k+1) and simplify to (k+1)/(k+2)
Assuming P(k): Σ_{r=1}^k 1/(r(r+1)) = k/(k+1). Adding the (k+1)th term gives k/(k+1) + 1/((k+1)(k+2)). Combining over common denominator (k+1)(k+2) yields [k(k+2)+1]/[(k+1)(k+2)] = (k^2+2k+1)/[(k+1)(k+2)] = (k+1)^2/[(k+1)(k+2)] = (k+1)/(k+2). Thus P(k+1) holds.
10. Define a sequence by a_1=1, a_2=3, a_{n+1}=a_n+a_{n-1} for n≥2. Which of the following is true for all n≥1?
- a_n < (2)^n
- a_n < (5/3)^n
- a_n < (3/2)^n
- a_n < (7/4)^n
Answer: a_n < (7/4)^n
Using strong induction: base cases n=1,2 hold. Assume a_k < (7/4)^k and a_{k-1} < (7/4)^{k-1}. Then a_{k+1} < (7/4)^k + (7/4)^{k-1} = (7/4)^{k-1}·11/4. Since (7/4)^2 = 49/16 > 44/16 = 11/4, we get a_{k+1} < (7/4)^{k+1}. Hence the inequality holds for all n.
11. For S_n = Σ_{r=1}^n 1/(r(r+1)), which method directly gives the sum?
- Telescoping: 1 - 1/(n+1) = n/(n+1)
- Partial fractions: 1/(r(r+1)) = 1/r - 1/(r+1)
- Both telescoping and induction give the same sum
- Induction: guess n/(n+1) and prove
Answer: Partial fractions: 1/(r(r+1)) = 1/r - 1/(r+1)
Partial fractions decompose 1/(r(r+1)) into 1/r - 1/(r+1). Substituting into the sum gives telescoping cancellation, directly yielding S_n = 1 - 1/(n+1) = n/(n+1). This is the most direct method as it provides the sum without guessing or induction.
12. In proving that every integer n ≥ 2 has a prime factorisation by strong induction, what is the inductive hypothesis used?
- Every integer from 2 to k-1 has a prime factorisation.
- Every integer from 2 to k has a prime factorisation.
- Every integer from 2 to k+1 has a prime factorisation.
- Every integer from 2 to k/2 has a prime factorisation.
Answer: Every integer from 2 to k has a prime factorisation.
In strong induction, we assume the statement holds for all smaller numbers. For proving P(k+1), we assume P(2), P(3),..., P(k) are true, i.e., every integer from 2 to k has a prime factorisation. This allows us to factorise a and b when k+1 = a·b.