Proof by Induction - Worksheets, Questions and Revision
32 original exam-style questions - 7 pages of questions with a full mark scheme - free printable PDF.
Proof by Induction revision guideWrite-in editionMore A Level Further Maths practiceMock exams
This topic is chapter 9 of A Level Further Maths Core Pure Topic Workbook and chapter 9 of A Level Further Maths 10-Minute Tests 1.
1.9 Proof by Induction
Question 1
- (a) LHS = 1, RHS = [1*2/2]2 = 1, so true for n=1B1
- (a) Answer: n = 1: LHS = 1, RHS = 1, statement holds.
- (b) assume true for n=k: T(k) = [k(k+1)/2]2, form T(k+1) = T(k) + (k+1)3M1
- (b) take out common factor (k+1)2: T(k+1) = (k+1)2[ k2/4 + (k+1) ]dM1
- (b) correct simplification to [(k+1)(k+2)/2]2 csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (b) Answer: T(k+1) = [(k+1)(k+2)/2]2; true for all positive integers n by induction.
- (c) [10(11)/2]2 = 552 = 3025 csoB1
- (c) 1+2+...+10 = 55, and 552 = 3025, so the two are equalB1
- (c) Answer: 3025; equals (55)2, confirming the identity.
Question 2
- (a) LHS = 1(2) = 2, RHS = (1/3)(1)(2)(3) = 2, so true for n=1B1
- (a) Answer: n = 1: LHS = 2, RHS = 2, statement holds.
- (b) assume true for n=k: U(k) = (1/3)k(k+1)(k+2), form U(k+1) = U(k) + (k+1)(k+2)M1
- (b) take out common factor (k+1)(k+2): U(k+1) = (k+1)(k+2)[ k/3 + 1 ]dM1
- (b) correct simplification to (1/3)(k+1)(k+2)(k+3) csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (b) Answer: U(k+1) = (1/3)(k+1)(k+2)(k+3); true for all positive integers n by induction.
- (c) substitute n=15 into (1/3)n(n+1)(n+2)M1
- (c) 1360 caoA1
- (c) Answer: 1360
Question 3
- (a) 32 - 1 = 8 = 8(1), which is divisible by 8B1
- (a) Answer: n = 1: 32 - 1 = 8, divisible by 8.
- (b) assume true for n=k: 32k - 1 = 8m for some positive integer m, so 32k = 8m + 1M1
- (b) write 32(k+1) - 1 = 9(32k) - 1M1
- (b) substitute 32k = 8m+1 to get 9(8m+1) - 1dM1
- (b) simplify to 72m + 8 = 8(9m+1), which is divisible by 8, csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (b) Answer: 32(k+1) - 1 = 8(9m+1); true for all positive integers n by induction.
- (c) n=2: 34 - 1 = 80B1
- (c) 80 / 24 is not an integer (80 = 24(3) + 8), so the statement is falseB1
- (c) Answer: False: 34 - 1 = 80, which is not divisible by 24.
Question 4
- (a) u2 = 2(5) - 3 and u3 = 2u2 - 3M1
- (a) u2 = 7, u3 = 11 caoA1
- (a) Answer: u2 = 7, u3 = 11
- (b) basis n=1: 21+3 = 5 = u1, trueB1
- (b) assume true for n=k: uk = 2k+3M1
- (b) substitute into recurrence: uk+1 = 2(2k+3) - 3dM1
- (b) simplify to 2k+1 + 3 csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (b) Answer: uk+1 = 2k+1+3; true for all positive integers n by induction.
Question 5
- (a) product rule: f'(x) = ex + x exM1
- (a) = (x+1)ex, which matches (x+n)ex with n=1A1
- (a) Answer: f'(x) = (x+1)ex
- (b) assume true for n=k: fk(x) = (x+k)exM1
- (b) differentiate using the product rule: fk+1(x) = ex + (x+k)exM1
- (b) simplify to (x+k+1)ex csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (b) Answer: fk+1(x) = (x+(k+1))ex; true for all positive integers n by induction.
Question 6
- (a) n=1: LHS=1, RHS=1; n=2: LHS=1-4=-3, RHS=(-1)(3)=-3, both trueB1
- (a) Answer: Both cases hold: n=1 gives 1=1; n=2 gives -3=-3.
- (b) 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)2M1
- (b) factor out (-1)k+1(k+1): A(k+1) = (-1)k+1(k+1)[ k/2 - (k+1) ]M1
- (b) simplify the bracket to -(k+2)/2 and combine the sign correctlydM1
- (b) simplify to (-1)k+2(k+1)(k+2)/2 csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (b) Answer: A(k+1) = (-1)(k+1)+1 (k+1)(k+2)/2; true for all positive integers n by induction.
Question 7
- (a) 5+9+2 = 16 = 4(4), divisible by 4B1
- (a) Answer: n = 1: 5 + 9 + 2 = 16, divisible by 4.
- (b) assume true for n=k: 5k+9k+2 = 4m for some positive integer mM1
- (b) consider 5k+1+9k+1+2 - 5(5k+9k+2) and expandM1
- (b) simplify this difference to 4(9k - 2)dM1
- (b) hence 5k+1+9k+1+2 = 5(4m) + 4(9k-2) = 4(5m+9k-2), divisible by 4, csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (b) Answer: 5k+1+9k+1+2 = 4(5m+9k-2); true for all positive integers n by induction.
Question 8
- (a) u1 = 3 x 30 - 1 = 2B1
- (a) Answer: true for n = 1
- (b) uk+1 = 3uk + 2 = 3(3 x 3k - 1 - 1) + 2M1
- (b) expands: 3 x 3k - 3 + 2M1
- (b) 2 - 3 = -1, giving 3 x 3k - 1A1
- (b) true for n = 1, true for n = k implies true for n = k + 1, so true for all n by induction (cso)A1
- (b) Answer: proved by induction
Question 9
- (a) f(1) = 5 x 1, divisible by 5B1
- (a) Answer: true for n = 1
- (b) assumes f(k) = m x (an integer) for some positive integer kM1
- (b) expresses f(k + 1) in terms of f(k): f(k + 1) = 6k + 1 - 1 = 6(6k - 1) + 5 = 6f(k) + 5M1
- (b) both terms are multiples of the divisor, so f(k + 1) is divisibleA1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 10
- (a) LHS = 6, RHS = 6, so true for n = 1B1
- (a) Answer: n = 1: both sides equal 6
- (b) assumes sum to k = k(k + 1)(2k + 16)/6 and adds the (k + 1)th termM1
- (b) factorises or expands to simplifyM1
- (b) obtains (k + 1)((k + 1) + 1)(2(k + 1) + 16)/6 by the simplification: k(k + 1)(2k + 16)/6 + (k + 1)(k + 6) = (k + 1)[k(2k + 16) + 6(k + 6)]/6 = (k + 1)(k + 2)(2k + 18)/6A1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 11
- (a) LHS = 2, RHS = 2, so true for n = 1B1
- (a) Answer: n = 1: both sides equal 2
- (b) assumes sum to k = 2k2(k + 1)2/4 and adds the (k + 1)th termM1
- (b) factorises or expands to simplifyM1
- (b) obtains 2(k + 1)2((k + 1) + 1)2/4 by the simplification: 2k2(k + 1)2/4 + 2(k + 1)3 = 2(k + 1)2[k2 + 4(k + 1)]/4 = 2(k + 1)2(k + 2)2/4A1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 12
- (a) evaluates the formula at n = 1: ((4, 0), (3, 1)) = MB1
- (a) Answer: true for n = 1
- (b) assumes Mk as the formula and writes Mk + 1 = Mk MM1
- (b) carries out the matrix multiplicationM1
- (b) simplifies the entries (bottom left: [(4k - 1)] x 4 + 3 = (4k + 1 - 1))A1
- (b) true for n = 1, true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 13
- (a) f(1) = 49 - 16 = 33, divisible by 33B1
- (a) Answer: true for n = 1
- (b) assumes f(k) = m x (an integer) for some positive integer kM1
- (b) expresses f(k + 1) in terms of f(k): f(k + 1) = 72k + 2 - 42k + 2 = 49f(k) + 42k(49 - 16) = 49f(k) + 33 x 42kM1
- (b) both terms are multiples of the divisor, so f(k + 1) is divisibleA1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 14
- (a) f(1) = 7 x 1, divisible by 7B1
- (a) Answer: true for n = 1
- (b) assumes f(k) = m x (an integer) for some positive integer kM1
- (b) expresses f(k + 1) in terms of f(k): f(k + 1) = 8k + 1 - 1 = 8(8k - 1) + 7 = 8f(k) + 7M1
- (b) both terms are multiples of the divisor, so f(k + 1) is divisibleA1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 15
- (a) n = 1: 2(3) + 1(5) = 11B1
- (a) n = 2: 2(9) + 1(25) = 43B1
- (a) Answer: true for n = 1 and n = 2
- (b) uk+2 = 8uk+1 - 15uk and substitutes the assumptionsM1
- (b) collects the r1 terms: 2 x 3k(8 x 3 - 15) = 2 x 3k + 2 since 32 - 8 x 3 + 15 = 0M1
- (b) similarly for the r2 terms, obtaining 2 x 3k + 2 + 1 x 5k + 2A1
- (b) true for n = 1, 2; true for n = k, k + 1 implies true for n = k + 2; so true for all positive integers n by induction (cso)A1
- (b) Answer: proved by induction
Question 16
- (a) n = 1: 2(3) - 2(5) = -4B1
- (a) n = 2: 2(9) - 2(25) = -32B1
- (a) Answer: true for n = 1 and n = 2
- (b) uk+2 = 8uk+1 - 15uk and substitutes the assumptionsM1
- (b) collects the r1 terms: 2 x 3k(8 x 3 - 15) = 2 x 3k + 2 since 32 - 8 x 3 + 15 = 0M1
- (b) similarly for the r2 terms, obtaining 2 x 3k + 2 - 2 x 5k + 2A1
- (b) true for n = 1, 2; true for n = k, k + 1 implies true for n = k + 2; so true for all positive integers n by induction (cso)A1
- (b) Answer: proved by induction
Question 17
- (a) LHS = 1, RHS = 1, so true for n = 1B1
- (a) Answer: n = 1: both sides equal 1
- (b) assumes sum to k = k2(k + 1)2/4 and adds the (k + 1)th termM1
- (b) factorises or expands to simplifyM1
- (b) obtains (k + 1)2((k + 1) + 1)2/4 by the simplification: k2(k + 1)2/4 + 1(k + 1)3 = 1(k + 1)2[k2 + 4(k + 1)]/4 = 1(k + 1)2(k + 2)2/4A1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 18
- (a) f(1) = 49 - 25 = 24, divisible by 24B1
- (a) Answer: true for n = 1
- (b) assumes f(k) = m x (an integer) for some positive integer kM1
- (b) expresses f(k + 1) in terms of f(k): f(k + 1) = 72k + 2 - 52k + 2 = 49f(k) + 52k(49 - 25) = 49f(k) + 24 x 52kM1
- (b) both terms are multiples of the divisor, so f(k + 1) is divisibleA1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 19
- (a) evaluates the formula at n = 1: ((2, 1), (0, 2)) = MB1
- (a) Answer: true for n = 1
- (b) assumes Mk as the formula and writes Mk + 1 = Mk MM1
- (b) carries out the matrix multiplicationM1
- (b) simplifies the entries (top right: 2k x 1 + k2k - 1 x 2 = (k + 1)2k)A1
- (b) true for n = 1, true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 20
- (a) f(1) = 49 - 36 = 13, divisible by 13B1
- (a) Answer: true for n = 1
- (b) assumes f(k) = m x (an integer) for some positive integer kM1
- (b) expresses f(k + 1) in terms of f(k): f(k + 1) = 72k + 2 - 62k + 2 = 49f(k) + 62k(49 - 36) = 49f(k) + 13 x 62kM1
- (b) both terms are multiples of the divisor, so f(k + 1) is divisibleA1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 21
- (a) n = 1: 1(2) + 1(5) = 7B1
- (a) n = 2: 1(4) + 1(25) = 29B1
- (a) Answer: true for n = 1 and n = 2
- (b) uk+2 = 7uk+1 - 10uk and substitutes the assumptionsM1
- (b) collects the r1 terms: 1 x 2k(7 x 2 - 10) = 1 x 2k + 2 since 22 - 7 x 2 + 10 = 0M1
- (b) similarly for the r2 terms, obtaining 1 x 2k + 2 + 1 x 5k + 2A1
- (b) true for n = 1, 2; true for n = k, k + 1 implies true for n = k + 2; so true for all positive integers n by induction (cso)A1
- (b) Answer: proved by induction
Question 22
- (a) evaluates the formula at n = 1: ((1, 2), (0, 1)) = MB1
- (a) Answer: true for n = 1
- (b) assumes Mk as the formula and writes Mk + 1 = Mk MM1
- (b) carries out the matrix multiplicationM1
- (b) simplifies the entries (top right: 1 x 2 + 2k x 1 = 2(k + 1))A1
- (b) true for n = 1, true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 23
- (a) u1 = 6 x 20 - 3 = 3B1
- (a) Answer: true for n = 1
- (b) uk+1 = 2uk + 3 = 2(6 x 2k - 1 - 3) + 3M1
- (b) expands: 6 x 2k - 6 + 3M1
- (b) 3 - 6 = -3, giving 6 x 2k - 3A1
- (b) true for n = 1, true for n = k implies true for n = k + 1, so true for all n by induction (cso)A1
- (b) Answer: proved by induction
Question 24
- (a) f(1) = 2 x 1, divisible by 2B1
- (a) Answer: true for n = 1
- (b) assumes f(k) = m x (an integer) for some positive integer kM1
- (b) expresses f(k + 1) in terms of f(k): f(k + 1) = 3k + 1 - 1 = 3(3k - 1) + 2 = 3f(k) + 2M1
- (b) both terms are multiples of the divisor, so f(k + 1) is divisibleA1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 25
- (a) LHS = 2, RHS = 2, so true for n = 1B1
- (a) Answer: n = 1: both sides equal 2
- (b) assumes sum to k = (k - 1)2k + 1 + 2 and adds the (k + 1)th termM1
- (b) factorises or expands to simplifyM1
- (b) obtains ((k + 1) - 1)2(k + 1) + 1 + 2 by the simplification: (k - 1)2k + 1 + 2 + (k + 1)2k + 1 = 2k + 1(2k) + 2 = k 2k + 2 + 2A1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 26
- (a) u1 = 5 x 30 - 3 = 2B1
- (a) Answer: true for n = 1
- (b) uk+1 = 3uk + 6 = 3(5 x 3k - 1 - 3) + 6M1
- (b) expands: 5 x 3k - 9 + 6M1
- (b) 6 - 9 = -3, giving 5 x 3k - 3A1
- (b) true for n = 1, true for n = k implies true for n = k + 1, so true for all n by induction (cso)A1
- (b) Answer: proved by induction
Question 27
- (a) LHS = 3/2, RHS = 3/2, so true for n = 1B1
- (a) Answer: n = 1: both sides equal 3/2
- (b) assumes sum to k = 3k/(k + 1) and adds the (k + 1)th termM1
- (b) factorises or expands to simplifyM1
- (b) obtains 3(k + 1)/((k + 1) + 1) by the simplification: 3k/(k + 1) + 3/((k + 1)(k + 2)) = 3[k(k + 2) + 1]/((k + 1)(k + 2)) = 3(k + 1)/(k + 2)A1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 28
- (a) evaluates the formula at n = 1: ((1, 5), (0, 1)) = MB1
- (a) Answer: true for n = 1
- (b) assumes Mk as the formula and writes Mk + 1 = Mk MM1
- (b) carries out the matrix multiplicationM1
- (b) simplifies the entries (top right: 1 x 5 + 5k x 1 = 5(k + 1))A1
- (b) true for n = 1, true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 29
- (a) evaluates the formula at n = 1: ((3, 0), (4, 1)) = MB1
- (a) Answer: true for n = 1
- (b) assumes Mk as the formula and writes Mk + 1 = Mk MM1
- (b) carries out the matrix multiplicationM1
- (b) simplifies the entries (bottom left: [2(3k - 1)] x 3 + 4 = 2(3k + 1 - 1))A1
- (b) true for n = 1, true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 30
- (a) f(1) = 25 - 16 = 9, divisible by 9B1
- (a) Answer: true for n = 1
- (b) assumes f(k) = m x (an integer) for some positive integer kM1
- (b) expresses f(k + 1) in terms of f(k): f(k + 1) = 52k + 2 - 42k + 2 = 25f(k) + 42k(25 - 16) = 25f(k) + 9 x 42kM1
- (b) both terms are multiples of the divisor, so f(k + 1) is divisibleA1
- (b) true for n = 1, and true for n = k implies true for n = k + 1, so true for all positive integers n by induction (cso)A1
- (b) Answer: result proved by induction
Question 31
- (a) multiply M by M to get M2 = ((9, 0), (4, 1))M1
- (a) (32-1)/2 = 4, matching the bottom-left entryA1
- (a) Answer: M2 = ((9, 0), (4, 1))
- (b) assume true for n=k: Mk = ((3k,0),((3k-1)/2,1)), form Mk+1 = Mk * MM1
- (b) carry out the matrix multiplication Mk * M correctlyM1
- (b) simplify the bottom-left entry: 3(3k-1)/2 + 1dM1
- (b) simplify to (3k+1-1)/2, and top-left to 3k+1, csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (b) Answer: Mk+1 = ((3k+1,0),((3k+1-1)/2,1)); true for all positive integers n by induction.
Question 32
- (a) for n=1, LHS = cos(θ)+isin(θ) = RHS = cos(1.θ)+isin(1.θ), so trueB1
- (a) Answer: n = 1: both sides equal cos(θ) + i sin(θ).
- (b) assume true for n=k: (cos θ + isin θ)k = cos(k θ)+isin(k θ)M1
- (b) write (cos θ+isin θ)k+1 = (cos(k θ)+isin(k θ))(cos θ+isin θ) and expandM1
- (b) collect real and imaginary parts using the addition formulaedM1
- (b) simplify to cos((k+1)θ) + isin((k+1)θ) csoA1
- (b) conclusion: true for n=1, true for n=k implies true for n=k+1, so true for all positive integers n by mathematical inductionA1
- (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) formula gives cos(0)+isin(0) = 1, consistent with z0 = 1 for any non-zero zB1
- (c) Answer: cos(0) + i sin(0) = 1, consistent with z0 = 1.
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.