Revision Library

revisionlibrary.co.uk

A-Level · Further Pure Mathematics

FP.CP9 Proof by Induction

EDEXCEL 9FM0 · Calculator allowed · about 120 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

Let S(n) = 1² + 2² + 3² + ... + n^2.

(a)Verify that the statement S(n) = (1/6)n(n+1)(2n+1) is true for n = 1.(1)

(b)Assuming the statement is true for n = k, prove that it is then true for n = k + 1, and hence prove by induction that S(n) = (1/6)n(n+1)(2n+1) for all positive integers n.(4)

(c)Hence find the value of 1² + 2² + ... + 20^2.(2)

(Total for Question 1 is 7 marks)

Let T(n) = 1³ + 2³ + 3³ + ... + n^3.

(a)Verify that the statement T(n) = [n(n+1)/2]² is true for n = 1.(1)

(b)Prove by induction that T(n) = [n(n+1)/2]² for all positive integers n.(4)

(c)Show that 1³ + 2³ + ... + 10³ = 3025, and verify that this equals (1 + 2 + ... + 10)^2.(2)

(Total for Question 2 is 7 marks)

Let U(n) = 1(2) + 2(3) + 3(4) + ... + n(n+1).

(a)Verify that the statement U(n) = (1/3)n(n+1)(n+2) is true for n = 1.(1)

(b)Prove by induction that U(n) = (1/3)n(n+1)(n+2) for all positive integers n.(4)

(c)Hence find the value of 1(2) + 2(3) + ... + 15(16).(2)

(Total for Question 3 is 7 marks)

Consider the statement P(n): 3²ⁿ - 1 is divisible by 8, for all positive integers n.

(a)Verify that P(1) is true.(1)

(b)Prove by induction that 3²ⁿ - 1 is divisible by 8 for all positive integers n.(5)

(c)By testing the case n = 2, determine whether the statement '3²ⁿ - 1 is divisible by 24 for all positive integers n' is true or false.(2)

(Total for Question 4 is 8 marks)

Consider the statement Q(n): n³ + 5n is divisible by 6, for all positive integers n.

(a)Verify that Q(1) is true.(1)

(b)Prove by induction that n³ + 5n is divisible by 6 for all positive integers n. You should explain clearly why any additional term you introduce is divisible by 6.(5)

(c)Hence explain briefly why n³ + 5n must also be an even number for every positive integer n.(1)

(Total for Question 5 is 7 marks)

A sequence is defined by u₁ = 5 and u_(n+1) = 2u_n - 3 for n ≥ 1.

(a)Find the values of u₂ and u₃.(2)

(b)Prove by induction that u_n = 2ⁿ + 3 for all positive integers n.(5)

(Total for Question 6 is 7 marks)

Let f(x) = x e^x.

(a)Using the product rule, find f'(x), and verify that this agrees with the formula fⁿ(x) = (x+n)e^x when n = 1.(2)

(b)Prove by induction that the nth derivative of f is fⁿ(x) = (x+n)e^x for all positive integers n.(4)

(Total for Question 7 is 6 marks)

The matrix M is given by M = ((3, 0), (1, 1)), where rows are written left to right, top row then bottom row.

(a)By direct matrix multiplication, find M², and verify that it agrees with the formula Mⁿ = ((3ⁿ, 0), ((3ⁿ - 1)/2, 1)) when n = 2.(2)

(b)Prove by induction that Mⁿ = ((3ⁿ, 0), ((3ⁿ - 1)/2, 1)) for all positive integers n.(5)

(Total for Question 8 is 7 marks)

You may use the addition formulae cos(A+B) = cosA cosB - sinA sinB and sin(A+B) = sinA cosB + cosA sinB.

(a)Verify that the statement (cos(θ) + i sin(θ))ⁿ = cos(n θ) + i sin(n θ) is true for n = 1.(1)

(b)Prove by induction that (cos(θ) + i sin(θ))ⁿ = cos(n θ) + i sin(n θ) for all positive integers n.(5)

(c)State the value predicted by the formula for (cos(θ) + i sin(θ))⁰, and confirm this is consistent with the usual convention for any non-zero complex number raised to the power 0.(1)

(Total for Question 9 is 7 marks)

Let A(n) = 1² - 2² + 3² - 4² + ... + (-1)ⁿ⁺¹ n² (i.e. the sum from r=1 to n of (-1)^r+1 r²).

(a)Verify that the statement A(n) = (-1)ⁿ⁺¹ n(n+1)/2 is true for n = 1 and for n = 2.(1)

(b)Prove by induction that A(n) = (-1)ⁿ⁺¹ n(n+1)/2 for all positive integers n.(5)

(Total for Question 10 is 6 marks)

Consider the statement R(n): n! > 3ⁿ, for integers n ≥ 7.

(a)Show that R(6) is false and that R(7) is true, and explain why n = 7 is the correct starting value for an induction proof of R(n).(2)

(b)Prove by induction that n! > 3ⁿ for all integers n ≥ 7.(5)

(Total for Question 11 is 7 marks)

Consider the statement W(n): 5ⁿ + 9ⁿ + 2 is divisible by 4, for all positive integers n.

(a)Verify that W(1) is true.(1)

(b)Prove by induction that 5ⁿ + 9ⁿ + 2 is divisible by 4 for all positive integers n.(5)

(Total for Question 12 is 6 marks)

A sequence is defined by a₁ = 1, a₂ = 1, and a_(n+2) = a_(n+1) + a_n for n ≥ 1 (the Fibonacci sequence).

(a)Find a₃ and a₄, and verify that a_n < 2ⁿ for n = 1, 2, 3 and 4.(2)

(b)Explain why, in order to prove a_(k+1) < 2^k+1 using the recurrence relation, it is necessary to assume the inequality is true for both n = k and n = k - 1, rather than for n = k alone.(1)

(c)Using this two-step approach, prove by induction that a_n < 2ⁿ for all positive integers n.(6)

(Total for Question 13 is 9 marks)

Mark scheme · FP.CP9 Proof by Induction

Question 1

(a) B1 LHS = 1, RHS = (1/6)(1)(2)(3) = 1, so true for n=1
(a) Answer: n = 1: LHS = 1, RHS = 1, statement holds.
(b) M1 assume true for n=k: S(k) = (1/6)k(k+1)(2k+1), then form S(k+1) = S(k) + (k+1)²
(b) dM1 factorise out (k+1): S(k+1) = (k+1)[ (1/6)k(2k+1) + (k+1) ], combine over common denominator 6
(b) A1 correct simplification to (1/6)(k+1)(k+2)(2k+3) cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction (dep on all previous marks)
(b) Answer: S(k+1) = (1/6)(k+1)(k+2)(2(k+1)+1); true for all positive integers n by induction.
(c) M1 substitute n=20 into (1/6)n(n+1)(2n+1)
(c) A1 2870 cao
(c) Answer: 2870

Question 2

(a) B1 LHS = 1, RHS = [1*2/2]² = 1, so true for n=1
(a) Answer: n = 1: LHS = 1, RHS = 1, statement holds.
(b) M1 assume true for n=k: T(k) = [k(k+1)/2]², form T(k+1) = T(k) + (k+1)³
(b) dM1 take out common factor (k+1)²: T(k+1) = (k+1)²[ k²/4 + (k+1) ]
(b) A1 correct simplification to [(k+1)(k+2)/2]² cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: T(k+1) = [(k+1)(k+2)/2]²; true for all positive integers n by induction.
(c) B1 [10(11)/2]² = 55² = 3025 cso
(c) B1 1+2+...+10 = 55, and 55² = 3025, so the two are equal
(c) Answer: 3025; equals (55)², confirming the identity.

Question 3

(a) B1 LHS = 1(2) = 2, RHS = (1/3)(1)(2)(3) = 2, so true for n=1
(a) Answer: n = 1: LHS = 2, RHS = 2, statement holds.
(b) M1 assume true for n=k: U(k) = (1/3)k(k+1)(k+2), form U(k+1) = U(k) + (k+1)(k+2)
(b) dM1 take out common factor (k+1)(k+2): U(k+1) = (k+1)(k+2)[ k/3 + 1 ]
(b) A1 correct simplification to (1/3)(k+1)(k+2)(k+3) cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: U(k+1) = (1/3)(k+1)(k+2)(k+3); true for all positive integers n by induction.
(c) M1 substitute n=15 into (1/3)n(n+1)(n+2)
(c) A1 1360 cao
(c) Answer: 1360

Question 4

(a) B1 3² - 1 = 8 = 8(1), which is divisible by 8
(a) Answer: n = 1: 3² - 1 = 8, divisible by 8.
(b) M1 assume true for n=k: 3^2k - 1 = 8m for some positive integer m, so 3^2k = 8m + 1
(b) M1 write 3^2(k+1) - 1 = 9(3^2k) - 1
(b) dM1 substitute 3^2k = 8m+1 to get 9(8m+1) - 1
(b) A1 simplify to 72m + 8 = 8(9m+1), which is divisible by 8, cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: 3^2(k+1) - 1 = 8(9m+1); true for all positive integers n by induction.
(c) B1 n=2: 3⁴ - 1 = 80
(c) B1 80 / 24 is not an integer (80 = 24(3) + 8), so the statement is false
(c) Answer: False: 3⁴ - 1 = 80, which is not divisible by 24.

Question 5

(a) B1 1³ + 5(1) = 6, which is divisible by 6
(a) Answer: n = 1: 1 + 5 = 6, divisible by 6.
(b) M1 assume true for n=k: k³ + 5k = 6m for some positive integer m, form (k+1)³ + 5(k+1)
(b) M1 expand and group as (k³+5k) + 3k² + 3k + 6 = 6m + 3k(k+1) + 6
(b) B1 explain that k(k+1) is a product of two consecutive integers so is always even, hence 3k(k+1) is divisible by 6
(b) A1 conclude (k+1)³+5(k+1) = 6(m + j + 1) for k(k+1)=2j, divisible by 6, cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: (k+1)³+5(k+1) = 6(m+j+1) where k(k+1)=2j; true for all positive integers n by induction.
(c) B1 since n³+5n is divisible by 6 = 2x3, it must be divisible by 2, so it is always even
(c) Answer: Any multiple of 6 is also a multiple of 2, so n³+5n is always even.

Question 6

(a) M1 u₂ = 2(5) - 3 and u₃ = 2u₂ - 3
(a) A1 u₂ = 7, u₃ = 11 cao
(a) Answer: u₂ = 7, u₃ = 11
(b) B1 basis n=1: 2¹+3 = 5 = u₁, true
(b) M1 assume true for n=k: u_k = 2^k+3
(b) dM1 substitute into recurrence: u_(k+1) = 2(2^k+3) - 3
(b) A1 simplify to 2^k+1 + 3 cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: u_(k+1) = 2^k+1+3; true for all positive integers n by induction.

Question 7

(a) M1 product rule: f'(x) = e^x + x e^x
(a) A1 = (x+1)e^x, which matches (x+n)e^x with n=1
(a) Answer: f'(x) = (x+1)e^x
(b) M1 assume true for n=k: f^k(x) = (x+k)e^x
(b) M1 differentiate using the product rule: f^k+1(x) = e^x + (x+k)e^x
(b) A1 simplify to (x+k+1)e^x cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: f^k+1(x) = (x+(k+1))e^x; true for all positive integers n by induction.

Question 8

(a) M1 multiply M by M to get M² = ((9, 0), (4, 1))
(a) A1 (3²-1)/2 = 4, matching the bottom-left entry
(a) Answer: M² = ((9, 0), (4, 1))
(b) M1 assume true for n=k: M^k = ((3^k,0),((3^k-1)/2,1)), form M^k+1 = M^k * M
(b) M1 carry out the matrix multiplication M^k * M correctly
(b) dM1 simplify the bottom-left entry: 3(3^k-1)/2 + 1
(b) A1 simplify to (3^k+1-1)/2, and top-left to 3^k+1, cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: M^k+1 = ((3^k+1,0),((3^k+1-1)/2,1)); true for all positive integers n by induction.

Question 9

(a) B1 for n=1, LHS = cos(θ)+isin(θ) = RHS = cos(1.θ)+isin(1.θ), so true
(a) Answer: n = 1: both sides equal cos(θ) + i sin(θ).
(b) M1 assume true for n=k: (cos θ + isin θ)^k = cos(k θ)+isin(k θ)
(b) M1 write (cos θ+isin θ)^k+1 = (cos(k θ)+isin(k θ))(cos θ+isin θ) and expand
(b) dM1 collect real and imaginary parts using the addition formulae
(b) A1 simplify to cos((k+1)θ) + isin((k+1)θ) cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: (cos θ+isin θ)^k+1 = cos((k+1)θ)+isin((k+1)θ); true for all positive integers n by induction (De Moivre's theorem).
(c) B1 formula gives cos(0)+isin(0) = 1, consistent with z⁰ = 1 for any non-zero z
(c) Answer: cos(0) + i sin(0) = 1, consistent with z⁰ = 1.

Question 10

(a) B1 n=1: LHS=1, RHS=1; n=2: LHS=1-4=-3, RHS=(-1)(3)=-3, both true
(a) Answer: Both cases hold: n=1 gives 1=1; n=2 gives -3=-3.
(b) M1 assume true for n=k: A(k) = (-1)^k+1 k(k+1)/2, form A(k+1) = A(k) + (-1)^k+2(k+1)²
(b) M1 factor out (-1)^k+1(k+1): A(k+1) = (-1)^k+1(k+1)[ k/2 - (k+1) ]
(b) dM1 simplify the bracket to -(k+2)/2 and combine the sign correctly
(b) A1 simplify to (-1)^k+2(k+1)(k+2)/2 cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: A(k+1) = (-1)^(k+1)+1 (k+1)(k+2)/2; true for all positive integers n by induction.

Question 11

(a) B1 n=6: 6≠720, 3⁶=729, so 720<729 and R(6) is false
(a) B1 n=7: 7≠5040, 3⁷=2187, so 5040>2187 and R(7) is true; n=7 is the smallest value for which the inequality holds, so it is the valid base case
(a) Answer: R(6) false (720 < 729); R(7) true (5040 > 2187); n=7 is the smallest valid base case.
(b) M1 assume true for n=k (k≥7): k! > 3^k, form (k+1)! = (k+1)*k!
(b) M1 use the assumption: (k+1)! > (k+1)*3^k
(b) dM1 argue that since k≥7, k+1≥8>3, so (k+1)*3^k > 3*3^k = 3^k+1
(b) A1 combine to give (k+1)! > 3^k+1 cso
(b) A1 conclusion: true for n=7, true for n=k implies true for n=k+1, so true for all integers n ≥ 7 by mathematical induction
(b) Answer: (k+1)! > 3^k+1; true for all integers n ≥ 7 by induction.

Question 12

(a) B1 5+9+2 = 16 = 4(4), divisible by 4
(a) Answer: n = 1: 5 + 9 + 2 = 16, divisible by 4.
(b) M1 assume true for n=k: 5^k+9^k+2 = 4m for some positive integer m
(b) M1 consider 5^k+1+9^k+1+2 - 5(5^k+9^k+2) and expand
(b) dM1 simplify this difference to 4(9^k - 2)
(b) A1 hence 5^k+1+9^k+1+2 = 5(4m) + 4(9^k-2) = 4(5m+9^k-2), divisible by 4, cso
(b) A1 conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical induction
(b) Answer: 5^k+1+9^k+1+2 = 4(5m+9^k-2); true for all positive integers n by induction.

Question 13

(a) M1 a₃ = a₂+a₁ = 2, a₄ = a₃+a₂ = 3
(a) A1 check each: 1<2, 1<4, 2<8, 3<16, all true cao
(a) Answer: a₃ = 2, a₄ = 3; inequality holds for n = 1, 2, 3, 4.
(b) B1 since a_(k+1) = a_k + a_(k-1), the recurrence involves two previous terms, so both a_k < 2^k and a_(k-1) < 2^k-1 are needed to bound a_(k+1); this requires two base cases and a two-step (strong) inductive hypothesis
(b) Answer: The recurrence a_(k+1) = a_k + a_(k-1) depends on two previous terms, so the inductive hypothesis must cover both n = k and n = k-1 (strong induction with two base cases).
(c) B1 basis n=1: a₁ = 1 < 2¹ = 2
(c) B1 basis n=2: a₂ = 1 < 2² = 4
(c) M1 assume true for n=k-1 and n=k (k≥2): a_(k-1)<2^k-1 and a_k<2^k
(c) M1 use the recurrence: a_(k+1) = a_k + a_(k-1) < 2^k + 2^k-1
(c) A1 since 2^k-1<2^k, 2^k+2^k-1 < 2^k+2^k = 2^k+1, so a_(k+1) < 2^k+1 cso
(c) A1 conclusion: true for n=1 and n=2, and true for n=k-1,k implies true for n=k+1, so true for all positive integers n by (strong) mathematical induction
(c) Answer: a_(k+1) < 2^k+1; true for all positive integers n by strong induction.

Proof by Induction - Worksheets, Questions and Revision