- 1
Let f(n)=5n+3 for positive integers n. It is to be proved by induction that f(n) is divisible by 4 for all n. (a)Find the value of f(3). [1 mark] - A128
- B18
- C125
- D512
Show the mark scheme
(b)Which statement is the correct inductive hypothesis?
[1 mark] - A5k+1+3 is divisible by 4
- B5k+3=4
- C5k+3=4k
- D5k+3=4m for some integer m
Show the mark scheme
(c)Assuming that f(k) is divisible by 4, show that f(k+1) is divisible by 4. [2 marks] Show the mark scheme
Mark scheme
M1: f(k+1)−f(k)=5k+1−5k=4×5k, or f(k+1)=5(4m−3)+3 using 5k+3=4m
A1: f(k+1)=4m+4×5k=4(m+5k), or 20m−12=4(5m−3), a multiple of 4
Accept: any correct argument that f(k+1) is an integer multiple of 4 Total for question 1: 4 marks
- 2
The matrix M=(1021) satisfies Mn=(102n1) for every positive integer n. - A(1081)
- B(1061)
- C(1021)
- D(1063)
Show the mark scheme
(b)In an inductive proof of the formula, the hypothesis is assumed for n=k. Which matrix is MkM? [1 mark] - A(104k1)
- B(102k1)
- C(102k+21)
- D(102k+22)
Show the mark scheme
(c)Find the smallest positive integer n for which the top-right entry of Mn is greater than 1000. [2 marks] Show the mark scheme
Mark scheme
M1: 2n>1000
A1: n=501
Do not accept: n=500, where the entry equals 1000 rather than exceeding it Total for question 2: 4 marks
- 3
Let A=(32−2−1). A student conjectures that An=(1+2n2n−2n1−2n) for all positive integers n. (a)Calculate A2 and A3, and show that the conjecture is correct for n=2 and n=3. [3 marks] Show the mark scheme
Mark scheme
M1: attempts A×A (or A2×A for the cube)
A1: A2=(54−4−3), matching the formula with n=2
A1: A3=(76−6−5), matching the formula with n=3 (b)Prove by induction that the conjecture is true for all positive integers n. [4 marks] Show the mark scheme
Mark scheme
B1: n=1: (1+22−21−2)=(32−2−1)=A, so true for n=1
M1: assumes true for n=k and forms Ak+1=AkA=(1+2k2k−2k1−2k)(32−2−1)
A1: =(3+2k2k+2−2k−2−2k−1), all four entries correct
A1: this equals (1+2(k+1)2(k+1)−2(k+1)1−2(k+1)), the formula with n=k+1; true for n=1 and true for n=k implies true for n=k+1, so true for all positive integers n by induction
Accept: Ak+1=AAk Total for question 3: 7 marks
- 4
Let f(n)=32n+7 and g(n)=n3+11n, where n is a positive integer. (a)Prove by induction that f(n) is divisible by 8 for all positive integers n. [6 marks] Show the mark scheme
Mark scheme
B1: f(1)=9+7=16=8×2, so true for n=1
M1: assumes f(k)=32k+7=8m for some integer m, and considers f(k+1)−f(k) (or f(k+1))
A1: f(k+1)−f(k)=32k+2−32k=8×32k
M1: f(k+1)=f(k)+8×32k=8m+8×32k
A1: =8(m+32k), a multiple of 8
A1: conclusion: true for n=1, and true for n=k implies true for n=k+1, so true for all positive integers n by induction (b)Prove by induction that g(n) is divisible by 6 for all positive integers n. [6 marks] Show the mark scheme
Mark scheme
B1: g(1)=1+11=12=6×2, so true for n=1
M1: assumes g(k)=6m for some integer m and forms g(k+1)−g(k)=(k+1)3+11(k+1)−k3−11k
A1: =3k2+3k+12=3k(k+1)+12
M1: k(k+1) is a product of consecutive integers so is even, k(k+1)=2j, so 3k(k+1)=6j
A1: g(k+1)=6m+6j+12=6(m+j+2), a multiple of 6
A1: conclusion: true for n=1, and true for n=k implies true for n=k+1, so true for all positive integers n by induction
Accept: checking separately that 3k(k+1) is divisible by 6 for even and odd k Total for question 4: 12 marks
End of questions