Questions on induction: divisibility and matrices

Question 1

Let f(n) = 8ⁿ − 1. Show that f(1) is divisible by 7, and write down the inductive hypothesis for the claim that 7 divides f(n) for all positive integers n.

Accepted Answer

f(1) = 8 − 1 = 7, which is divisible by 7. Hypothesis: assume f(k) = 8^k − 1 is divisible by 7 for some positive integer k. B1 for the base case, B1 for the hypothesis.

Question 2

Using f(n) = 8ⁿ − 1, simplify f(k + 1) − 8f(k) and hence complete the divisibility proof.

Accepted Answer

f(k + 1) − 8f(k) = (8^k+1 − 1) − (8^k+1 − 8) = 7. So f(k + 1) = 8f(k) + 7, a multiple of 7 plus 7, and so divisible by 7. With the base case, 7 divides 8ⁿ − 1 for all n. M1 for forming f(k + 1) − 8f(k), A1 for the constant remainder, A1 for the conclusion.

Question 3

Evaluate 2ⁿ and n² for n = 1, 2, 3, 4 and 5, and state the smallest value of n from which 2ⁿ > n² appears to hold for every larger n as well.

Accepted Answer

n = 1: 2 and 1, so 2 > 1. n = 2: 4 and 4, equal, so the inequality fails. n = 3: 8 and 9, so 2ⁿ is smaller. n = 4: 16 and 16, equal again. n = 5: 32 and 25, so 2ⁿ > n² once more. B1 for all five pairs of values. The inequality holds at n = 1, fails at n = 2, 3 and 4, with two of those failures being ties rather than 2ⁿ being smaller, and holds again from n = 5. B1 for reading off where it fails. So n = 5 is the smallest value from which the pattern seems to continue. B1 for n = 5. Checking further values is evidence for a proof starting there, not a proof by itself.

Question 4

The statement '4ⁿ + 1 is divisible by 3' satisfies the inductive step, since 4^k+1 + 1 = 4(4^k + 1) − 3 expresses the k + 1 case as a multiple of the k case plus a multiple of 3. Explain why the statement is nevertheless false for every positive integer n.

Accepted Answer

The base case fails: at n = 1, 4 + 1 = 5, which is not divisible by 3. B1 for checking n = 1 and finding it false. The inductive step only ever passes a property along a chain; with no true case to start the chain, the step has nothing to propagate, and truth at k + 1 is never established for any k. B1 for that explanation. In fact 4ⁿ + 1 leaves remainder 2 on division by 3 for every n, base case included. B1 for stating that the statement is false at every n, not merely unproved.

Question 5

Prove by induction that 3²ⁿ + 7 is divisible by 8 for all positive integers n.

Accepted Answer

Base: 3² + 7 = 16 = 8 × 2. Step: with f(k) = 3^2k + 7 assumed divisible by 8, f(k + 1) = 9 × 3^2k + 7 = 9f(k) − 56. Both terms are multiples of 8 (56 = 8 × 7), so f(k + 1) is too. B1 for the base case, M1 for writing f(k + 1) in terms of f(k), A1 for 9f(k) − 56, A1 for both terms being multiples of 8, A1 for the conclusion. The multiplier 9 comes from 3^2(k+1) = 9 × 3^2k: each step multiplies the power part by 9.

Question 6

Let M be the matrix with rows (1, 1) and (0, 1). Prove by induction that Mⁿ has rows (1, n) and (0, 1).

Accepted Answer

Base: M¹ has rows (1, 1), (0, 1), matching n = 1. Step: assume M^k has rows (1, k), (0, 1). Then M^k+1 = M^kM multiplies to rows (1, k + 1), (0, 1), since the top-right entry is 1 × 1 + k × 1 = k + 1 and the rest are unchanged. So the pattern holds for all n. B1 for the base case, M1 for writing M^k+1 = M^kM, A1 for the top-right entry, A1 for the required form, A1 for the conclusion.

Question 7

Let D be the matrix with rows (2, 0) and (0, 3). Prove by induction that Dⁿ has rows (2ⁿ, 0) and (0, 3ⁿ).

Accepted Answer

Base: D¹ has rows (2, 0), (0, 3) = (2¹, 0), (0, 3¹). Step: assume the result at k; multiplying by D scales the top-left entry by 2 and the bottom-right by 3, giving 2^k+1 and 3^k+1 with the zeros preserved. B1 for the base case, M1 for multiplying by D, A1 for the top-left entry, A1 for the bottom-right entry, A1 for the conclusion.

Question 8

In divisibility proofs the working often forms f(k + 1) − m f(k) for a chosen multiplier m. Explain how m is chosen, and why the manoeuvre works.

Accepted Answer

Choose m to match the growth of the power term, so the powers cancel. For 8ⁿ − 1 take m = 8, for 3²ⁿ + 7 take m = 9. What remains is a constant, and if that constant is divisible by the target then f(k + 1) = m f(k) + constant inherits divisibility from the hypothesis. B1 for choosing m to match the growth of the power term, B1 for the powers cancelling to leave a constant, B1 for that constant carrying the divisibility.

Question 9

Let P be the matrix with rows (3, 1) and (0, 3). Prove by induction that Pⁿ has rows (3ⁿ, n × 3ⁿ⁻¹) and (0, 3ⁿ) for all positive integers n.

Accepted Answer

Base: n = 1. The claimed matrix has rows (3, 1 × 3⁰) = (3, 1) and (0, 3), which is P itself. B1. Step: assume P^k has rows (3^k, k × 3^k−1) and (0, 3^k). Then P^k+1 = P^kP, and multiplying gives top-left entry 3^k × 3 + k × 3^k−1 × 0 = 3^k+1. M1 for forming P^kP, A1 for the top-left entry. The top-right entry is 3^k × 1 + k × 3^k−1 × 3 = 3^k + k × 3^k = (k + 1) × 3^k, matching the required form with n = k + 1 written as (k + 1) × 3^(k+1)−1. A1 for the top-right entry. The bottom row is unchanged at (0, 3^k+1), since the bottom-left entry of P is 0. A1 for the bottom row. So the pattern holds for n = k + 1, and with the base case, for all positive integers n by induction. A1 for the conclusion.

Question 10

Prove by induction that 6ⁿ − 5n − 1 is divisible by 25 for all positive integers n.

Accepted Answer

Base: n = 1. 6 − 5 − 1 = 0, and 0 = 25 × 0 is a multiple of 25. B1. Step: assume 6^k − 5k − 1 = 25m for an integer m. Then 6^k+1 − 5(k + 1) − 1 = 6 × 6^k − 5k − 6. M1 for writing the k + 1 expression out in full. Rewriting 6 × 6^k as 6(6^k − 5k − 1) + 6(5k + 1), this becomes 6(6^k − 5k − 1) + 30k + 6 − 5k − 6 = 6 × 25m + 25k = 25(6m + k). M1 for the rearrangement around the hypothesis, A1 for the constant and linear terms combining to 25k, A1 for the factorised form 25(6m + k). This is a multiple of 25, so true for n = k + 1. With the base case, 6ⁿ − 5n − 1 is divisible by 25 for all positive integers n by induction. A1 for the conclusion. The linear term −5n does not simply cancel the way a constant does; splitting 6 × 6^k to expose both 6(6^k − 5k − 1) and the extra 5k is what a divisibility proof with an n-dependent remainder needs.

Question 11

Prove by induction that n! > 2ⁿ for all integers n ≥ 4.

Accepted Answer

Base: n = 4. 4! = 24 and 2⁴ = 16, and 24 > 16. B1. Step: assume k! > 2^k for some integer k ≥ 4. Then (k + 1)! = (k + 1) × k! > (k + 1) × 2^k, using the assumption. M1 for using the assumption first. Second inequality: since k ≥ 4, k + 1 ≥ 5 > 2, so (k + 1) × 2^k > 2 × 2^k = 2^k+1. M1 for the second inequality, stated explicitly. Chaining the two, (k + 1)! > (k + 1) × 2^k > 2^k+1, the statement at n = k + 1. A1 for the chain. True at n = 4 and inherited from k to k + 1, so n! > 2ⁿ for all integers n ≥ 4 by induction. A1 for the conclusion with the range.

Question 12

M is the matrix with rows (3, −4) and (1, −1). Prove by induction that Mⁿ has rows (1 + 2n, −4n) and (n, 1 − 2n) for all positive integers n.

Accepted Answer

Base: at n = 1 the formula gives rows (3, −4) and (1, −1), which is M. Step: assume M^k has rows (1 + 2k, −4k) and (k, 1 − 2k). Then M^k+1 = M^kM, and the four entries are 3(1 + 2k) − 4k = 3 + 2k, −4(1 + 2k) + 4k = −4 − 4k, 3k + (1 − 2k) = k + 1 and −4k − (1 − 2k) = −1 − 2k. Rewriting, 3 + 2k = 1 + 2(k + 1), −4 − 4k = −4(k + 1) and −1 − 2k = 1 − 2(k + 1), so the rows are (1 + 2(k + 1), −4(k + 1)) and (k + 1, 1 − 2(k + 1)), the formula at n = k + 1. True at n = 1 and inherited at every step, so true for all positive integers n. B1 for the base case, M1 for forming M^kM, M1 for at least one correct entry, A1 A1 for all four entries, A1 for rewriting them in terms of k + 1, A1 for the conclusion. Write M^k+1 as M^kM rather than MM^k and the hypothesis sits ready on the left; either order works here, but matrices do not commute in general, so the product is worth writing down explicitly rather than assuming.

Question 13

Prove that 2ⁿ > n³ for all integers n ≥ 10.

Accepted Answer

Base: n = 10. 2¹⁰ = 1024 and 10³ = 1000, and 1024 > 1000. B1. Step: assume 2^k > k³ for some integer k ≥ 10. Then 2^k+1 = 2 × 2^k > 2k³, using the assumption. M1 for using the assumption first. Second inequality: 2k³ > (k + 1)³ rearranges to 2 > (1 + 1/k)³, dividing both sides by k³. For k ≥ 10, 1/k ≤ 1/10, so 1 + 1/k ≤ 1.1, and 1.1³ = 1.331 < 2. M1 for the second inequality with the bound checked. So 2k³ > (k + 1)³. A1 for that step. Chaining the two, 2^k+1 > 2k³ > (k + 1)³, the statement at n = k + 1. A1 for the chain. True at n = 10 and inherited from k to k + 1, so 2ⁿ > n³ for all integers n ≥ 10 by induction. A1 for the conclusion with the range. The statement is also true in isolation at n = 1, but it fails for n = 2 up to n = 9, so a base case there would prove nothing about n = 10 onward; the range has to start where the inequality starts holding for good.

Question 14

Prove by induction that 3²ⁿ⁺¹ + 2ⁿ⁺² is divisible by 7 for all positive integers n.

Accepted Answer

Base: n = 1. 3³ + 2³ = 27 + 8 = 35 = 7 × 5, divisible by 7. B1. Step: assume 3^2k+1 + 2^k+2 = 7m for an integer m. Then 3^2k+3 + 2^k+3 = 9 × 3^2k+1 + 2 × 2^k+2. M1 for writing the k + 1 expression in terms of 3^2k+1 and 2^k+2. Rewriting the first term as 9(3^2k+1 + 2^k+2) − 9 × 2^k+2, the whole expression becomes 9(3^2k+1 + 2^k+2) − 9 × 2^k+2 + 2 × 2^k+2 = 9 × 7m − 7 × 2^k+2 = 7(9m − 2^k+2). M1 for the rearrangement around the hypothesis, A1 for combining −9 × 2^k+2 + 2 × 2^k+2 to −7 × 2^k+2, A1 for the factorised form 7(9m − 2^k+2). This is a multiple of 7, so true for n = k + 1. With the base case, 3²ⁿ⁺¹ + 2ⁿ⁺² is divisible by 7 for all positive integers n by induction. A1 for the conclusion. Two exponential terms have to be handled together here, since neither 3²ⁿ⁺¹ nor 2ⁿ⁺² is divisible by 7 on its own; only their sum is.

Question 15

N is the matrix with rows (2, 3) and (0, −1). Prove by induction that Nⁿ has rows (2ⁿ, 2ⁿ − (−1)ⁿ) and (0, (−1)ⁿ) for all positive integers n.

Accepted Answer

Base: n = 1. The claimed matrix has rows (2, 2 − (−1)) = (2, 3) and (0, −1), which is N itself. B1. Step: assume N^k has rows (2^k, 2^k − (−1)^k) and (0, (−1)^k). Then N^k+1 = N^kN, and the top-left entry is 2^k × 2 + 0 × 0 = 2^k+1. M1 for forming N^kN, A1 for the top-left entry. The top-right entry is 2^k × 3 + (2^k − (−1)^k) × (−1) = 3 × 2^k − 2^k + (−1)^k = 2 × 2^k + (−1)^k = 2^k+1 + (−1)^k, which equals 2^k+1 − (−1)^k+1, the required form with n = k + 1. A1 for the top-right entry. The bottom row is (0, (−1)^k × (−1)) = (0, (−1)^k+1). A1 for the bottom row. So the pattern holds for n = k + 1, and with the base case, for all positive integers n by induction. A1 for the conclusion.