Free worked solutions · 2026 Edition

IB Maths HL Paper 3 Chapter 4: Sequences, recurrences and proof by induction worked solutions

Worked solutions to the investigations in Chapter 4 of Photon Guidebook: Mathematics HL Paper 3 for the IB Diploma (2026 Edition). Each solution shows every step with the mark it earns, the way an IB mark scheme does.

Chapter 4 of 18
8 practice questions
2 Going further
Free, no sign-up

Start with Investigations All 18 chapters

Investigations

The practice investigations of the chapter, each with its full worked solution and mark scheme.

Investigation 1

[16 marks]

This question asks you to prove a divisibility result and then find every version of it that works.

(a) Show that 3^{2n+1}+2^{n+2} is divisible by 7 for n=0,\,1 and 2.

[2]

(b) Prove by mathematical induction that 3^{2n+1}+2^{n+2} is divisible by 7 for all n\in\mathbb{N}.

[6]

(c) Show that 9^n-2^n is divisible by 7 for all n\in\mathbb{N}.

[3]

(d) Hence find all integers a with 1\le a\le20 such that 3^{2n+1}+a\times2^n is divisible by 7 for all n\in\mathbb{N}.

[5]

Show solutionHide solution

(a) n=0: 3+4=7; n=1: 27+8=35; n=2: 243+16=259 (M1). These are 7\times1, 7\times5 and 7\times37 (A1).

(b) n=0: 3+4=7, divisible by 7 (A1). Assume 3^{2k+1}+2^{k+2}=7m for some integer m (M1). Then 3^{2k+3}+2^{k+3}=9\times3^{2k+1}+2\times2^{k+2} (M1) =9\left(7m-2^{k+2}\right)+2\times2^{k+2} (M1) =63m-7\times2^{k+2}=7\left(9m-2^{k+2}\right) (A1), a multiple of 7. True for n=0, and true for n=k leads to true for n=k+1, so true for all n\in\mathbb{N} (R1).

(c) 9^n-2^n=(9-2)\left(9^{n-1}+9^{n-2}\times2+\dots+2^{n-1}\right) (M1). The first factor is 7 (A1). The second factor is an integer for n\ge1, and for n=0 the expression is 0, which is divisible by 7 (R1).

(d) 3^{2n+1}=3\times9^n, so 3^{2n+1}+a\times2^n=3\left(9^n-2^n\right)+(3+a)2^n (M1 A1). The first term is divisible by 7 by part (c) (R1). With n=0 the whole expression is 3+a, so 7\mid(3+a) is necessary; it is also sufficient, because then (3+a)2^n is a multiple of 7 for every n (R1). 3+a\in\{7,14,21\} gives a=4,\,11,\,18 (A1).

Final answer

Sevens. (a) 7,\,35,\,259. (c) 9-2=7 is a factor. (d) 3^{2n+1}+a2^n=3(9^n-2^n)+(3+a)2^n, so 7\mid3+a: a=4,\,11,\,18.

Investigation 2

[16 marks]

This question asks you to find and prove a formula for a sum whose terms are fractions.

Let S_n=\displaystyle\sum_{k=1}^{n}\dfrac{1}{k(k+2)}, for n\in\mathbb{Z}^+.

(a) Find S_1, S_2 and S_3 as fractions.

[2]

(b) Prove by induction that S_n=\dfrac{n(3n+5)}{4(n+1)(n+2)}.

[6]

(c) Show that \dfrac{1}{k(k+2)}=\dfrac12\left(\dfrac1k-\dfrac1{k+2}\right), and hence find S_n without induction.

[4]

(d) Find \displaystyle\lim_{n\to\infty}S_n.

[1]

(e) Find the smallest value of n with S_n>0.74.

[3]

Show solutionHide solution

(a) S_1=\dfrac13 (A1). S_2=\dfrac13+\dfrac18=\dfrac{11}{24} and S_3=\dfrac{11}{24}+\dfrac1{15}=\dfrac{21}{40} (A1).

(b) n=1: \dfrac{1\times8}{4\times2\times3}=\dfrac13=S_1 (A1). Assume S_k=\dfrac{k(3k+5)}{4(k+1)(k+2)} (M1). Then S_{k+1}=\dfrac{k(3k+5)}{4(k+1)(k+2)}+\dfrac1{(k+1)(k+3)} (M1) =\dfrac{k(3k+5)(k+3)+4(k+2)}{4(k+1)(k+2)(k+3)} (A1). The numerator is 3k^3+14k^2+19k+8=(k+1)\left(3k^2+11k+8\right)=(k+1)^2(3k+8) (A1), so S_{k+1}=\dfrac{(k+1)(3k+8)}{4(k+2)(k+3)}, which is the formula with n=k+1. True for n=1, and true for n=k leads to true for n=k+1, so true for all n\in\mathbb{Z}^+ (R1).

(c) \dfrac12\left(\dfrac1k-\dfrac1{k+2}\right)=\dfrac12\times\dfrac{(k+2)-k}{k(k+2)} (M1) =\dfrac1{k(k+2)} (AG). Writing out the terms, only \dfrac11, \dfrac12, -\dfrac1{n+1} and -\dfrac1{n+2} survive (M1), so S_n=\dfrac12\left(\dfrac32-\dfrac1{n+1}-\dfrac1{n+2}\right) (A1) =\dfrac34-\dfrac{2n+3}{2(n+1)(n+2)} (A1).

(d) The subtracted term tends to 0, so S_n\to\dfrac34 (A1).

(e) S_n>0.74\iff\dfrac{2n+3}{2(n+1)(n+2)}<0.01 (M1). This gives n^2-97n-148>0 (A1), true first at n=99 (the left side is −50 at n=98 and 50 at n=99) (A1).

Final answer

Gaps of two. (a) \frac13,\,\frac{11}{24},\,\frac{21}{40}. (c) S_n=\frac12\left(\frac32-\frac1{n+1}-\frac1{n+2}\right). (d) \frac34. (e) n=99.

Investigation 3

[18 marks]

This question asks you to count the regions into which lines and circles divide the plane.

n straight lines are drawn in a plane so that no two are parallel and no three meet at a point. Let R_n be the number of regions formed.

(a) Draw diagrams to find R_1, R_2, R_3 and R_4.

[2]

(b) Explain why R_{n+1}=R_n+n+1.

[3]

(c) Prove by induction that R_n=\dfrac{n^2+n+2}{2}.

[5]

n circles are drawn so that every two circles meet at two points and no three circles meet at a point. Let C_n be the number of regions formed, including the region outside all the circles.

(d) Find C_1, C_2 and C_3, and explain why C_{n+1}=C_n+2n.

[4]

(e) Find and prove a formula for C_n.

[4]

Show solutionHide solution

(a) Diagrams show R_1=2 and R_2=4 (A1), R_3=7 and R_4=11 (A1).

(b) The new line meets each of the n existing lines once, in n distinct points (M1). These points cut the new line into n+1 pieces (A1). Each piece splits one old region into two, so n+1 regions are added (A1).

(c) n=1: \dfrac{1+1+2}{2}=2=R_1 (A1). Assume R_k=\dfrac{k^2+k+2}{2} (M1). Then R_{k+1}=R_k+k+1 by (b) (M1) =\dfrac{k^2+k+2+2k+2}{2}=\dfrac{k^2+3k+4}{2} (A1), and (k+1)^2+(k+1)+2=k^2+3k+4, so the formula holds for n=k+1. True for n=1, and true for n=k leads to true for n=k+1, so true for all n\in\mathbb{Z}^+ (R1).

(d) C_1=2, C_2=4 and C_3=8 (A1). The new circle meets each of the n old circles in 2 points: 2n points (M1), which cut it into 2n arcs (A1). Each arc splits one region into two, so 2n regions are added (R1).

(e) The values 2,4,8 and the rule C_{n+1}-C_n=2n (differences 2,4) suggest C_n=n^2-n+2 (M1). n=1: 1-1+2=2 (A1). Assume C_k=k^2-k+2; then C_{k+1}=k^2-k+2+2k (M1) =(k+1)^2-(k+1)+2 (A1), so by induction the formula holds for all n\in\mathbb{Z}^+.

Final answer

Lines and circles in the plane. (a) 2,\,4,\,7,\,11. (b) the new line crosses n lines so lies in n+1 regions. (d) 2,\,4,\,8. (e) C_n=n^2-n+2.

Investigation 4

[20 marks]

This question asks you to prove identities for a sequence that obeys the Fibonacci rule but starts differently.

The sequence L_n is defined by L_1=1, L_2=3 and L_{n+2}=L_{n+1}+L_n for n\ge1.

(a) Write down L_3 to L_8.

[1]

(b) Show that \sum_{i=1}^{n}L_i=L_{n+2}-3 for n=1,\,2,\,3, and prove it for all n\in\mathbb{Z}^+ by induction.

[5]

(c) Suggest and prove a similar formula for \sum_{i=1}^{n}L_i^2 in terms of L_n and L_{n+1}.

[6]

(d) Use your GDC to find \dfrac{L_{n+1}}{L_n} for n=5,\,10 and 15, and suggest the limit.

[3]

(e) Assuming the limit exists, prove that it equals \dfrac{1+\sqrt5}{2}.

[5]

Show solutionHide solution

(a) 4,\,7,\,11,\,18,\,29,\,47 (A1).

(b) n=1: 1=4-3; n=2: 1+3=4=7-3; n=3: 1+3+4=8=11-3 (A1). The case n=1 is the base case. Assume \sum_{i=1}^{k}L_i=L_{k+2}-3 (M1). Then \sum_{i=1}^{k+1}L_i=L_{k+2}-3+L_{k+1} (M1) =L_{k+3}-3 by the recurrence (A1). True for n=1, and true for n=k leads to true for n=k+1, so true for all n\in\mathbb{Z}^+ (R1).

(c) The sums are 1,\,10,\,26,\,75 and L_nL_{n+1}-2 is 1,\,10,\,26,\,75 for n=1,\dots,4; so suggest \sum_{i=1}^{n}L_i^2=L_nL_{n+1}-2 (M1 A1). Base case n=1 is among these. Assume true for n=k (M1). Then \sum_{i=1}^{k+1}L_i^2=L_kL_{k+1}-2+L_{k+1}^2 (M1) =L_{k+1}(L_k+L_{k+1})-2=L_{k+1}L_{k+2}-2 (A1). True for n=1, and true for n=k leads to true for n=k+1, so true for all n (R1).

(d) Generate L_n to L_{16} and divide (M1): 1.63636, 1.61789, 1.61804 (A1). The ratios settle at 1.618 (A1).

(e) Divide the recurrence by L_{n+1}: \dfrac{L_{n+2}}{L_{n+1}}=1+\dfrac{L_n}{L_{n+1}} (M1). If the ratio tends to \lambda, then \lambda=1+\dfrac1\lambda (A1). So \lambda^2-\lambda-1=0 (A1) and \lambda=\dfrac{1\pm\sqrt5}{2} (A1). The ratio of positive terms is positive, so \lambda=\dfrac{1+\sqrt5}{2} (R1).

Final answer

A cousin of Fibonacci. (a) 4,\,7,\,11,\,18,\,29,\,47. (c) \sum L_i^2=L_nL_{n+1}-2. (d) 1.63636,\,1.61789,\,1.61804; limit 1.618. (e) \lambda=1+\frac1\lambda, so \lambda^2-\lambda-1=0, positive root.

Investigation 5

[22 marks]

This question asks you to count binary strings that never have two ones in a row, and to study how that count grows.

A binary string is a list of digits, each 0 or 1. Let a_n be the number of strings of length n that do not contain two consecutive 1s. For example, 0101 counts and 0110 does not.

(a) List the strings counted by a_1, a_2 and a_3, and write down their numbers.

[2]

(b) Explain why a_n=a_{n-1}+a_{n-2} for n\ge3.

[4]

(c) Find a_4 to a_8.

[1]

(d) Prove by induction that a_1+a_2+\dots+a_n=a_{n+2}-3 for all n\in\mathbb{Z}^+.

[5]

(e) Prove by induction that a_n>\left(\dfrac32\right)^n for all n\in\mathbb{Z}^+.

[5]

(f) A string of length 10 is picked at random, every string being equally likely. Calculate the probability that it has no two consecutive 1s.

[2]

(g) Use your GDC to find the least n for which fewer than 1% of the strings of length n have no two consecutive 1s.

[3]

Show solutionHide solution

(a) n=1: 0, 1; n=2: 00, 01, 10; n=3: 000, 001, 010, 100, 101 (A1). So a_1=2, a_2=3, a_3=5 (A1).

(b) Split by the last digit of a valid string of length n (M1). If it is 0, the first n-1 digits form any valid string: a_{n-1} ways (A1). If it is 1, the digit before it must be 0, and the first n-2 digits form any valid string: a_{n-2} ways (A1). The cases are exhaustive and cannot overlap, so a_n=a_{n-1}+a_{n-2} (R1).

(c) a_4=8, a_5=13, a_6=21, a_7=34, a_8=55 (A1).

(d) n=1: a_1=2 and a_3-3=2 (A1). Assume \sum_{i=1}^{k}a_i=a_{k+2}-3 (M1). Then \sum_{i=1}^{k+1}a_i=a_{k+2}-3+a_{k+1} (M1) =a_{k+3}-3 (A1). True for n=1, and true for n=k leads to true for n=k+1, so true for all n (R1).

(e) n=1: 2>1.5; n=2: 3>2.25 (A1). Assume true for n=k-1 and n=k, where k\ge2 (M1). Then a_{k+1}=a_k+a_{k-1}>\left(\tfrac32\right)^k+\left(\tfrac32\right)^{k-1} (M1) =\left(\tfrac32\right)^{k-1}\times\tfrac52>\left(\tfrac32\right)^{k-1}\times\tfrac94=\left(\tfrac32\right)^{k+1} (A1). True for n=1,2, and if true for n=k-1 and n=k then true for n=k+1, so true for all n (R1).

(f) a_9=89 and a_{10}=144 from the recurrence (M1). The probability is \dfrac{144}{2^{10}}=\dfrac9{64}=0.141 (A1).

(g) The proportion is \dfrac{a_n}{2^n} (M1). For n=22 it is \dfrac{46\,368}{2^{22}}=0.01105, which is not below 1% (A1). For n=23 it is \dfrac{75\,025}{2^{23}}=0.00894, so n=23 (A1).

Final answer

Strings with no pair of ones. (a) 2,\,3,\,5. (b) split by the last digit. (c) 8,\,13,\,21,\,34,\,55. (f) \frac9{64}=0.141. (g) n=23.

Investigation 6

[22 marks]

This question asks you to bound a sum that has no simple closed form, first by induction and then by telescoping.

Let S_n=\displaystyle\sum_{k=1}^{n}\dfrac1{k^2}, for n\in\mathbb{Z}^+.

(a) Find S_1, S_2, S_3 and S_4 as fractions.

[2]

(b) Verify that S_n<2 for n=1,\dots,4. Explain why an induction that assumes S_k<2 cannot prove that S_{k+1}<2.

[3]

(c) Prove by induction that S_n\le2-\dfrac1n for all n\in\mathbb{Z}^+.

[6]

(d) Hence state a bound for S_n that does not depend on n.

[1]

(e) Show that \dfrac1{k^2}<\dfrac1{k-1}-\dfrac1k for k\ge2, and use telescoping to give a second proof that S_n<2-\dfrac1n for n\ge2.

[4]

The sequence S_n is increasing and bounded above, so it has a limit L.

(f) By considering S_m-S_n for m>n, show that L-S_n\le\dfrac1n. Hence find numbers a and b, to three significant figures, such that a<L\le b.

[4]

(g) Find the least value of n for which part (f) guarantees that L-S_n<0.001.

[2]

Show solutionHide solution

(a) S_1=1, S_2=\dfrac54, S_3=\dfrac{49}{36}, S_4=\dfrac{205}{144} (M1 A1).

(b) The values are 1,\,1.25,\,1.36,\,1.42, all below 2 (A1). If S_k<2 then S_{k+1}=S_k+\dfrac1{(k+1)^2}<2+\dfrac1{(k+1)^2} (M1), which is not below 2: the assumption leaves no room for the extra term, so a stronger statement is needed (R1).

(c) n=1: S_1=1\le2-1 (A1). Assume S_k\le2-\dfrac1k (M1). Then S_{k+1}\le2-\dfrac1k+\dfrac1{(k+1)^2} (M1). This is at most 2-\dfrac1{k+1} if \dfrac1{(k+1)^2}\le\dfrac1k-\dfrac1{k+1}=\dfrac1{k(k+1)} (A1), which is true because k(k+1)\le(k+1)^2 (A1). True for n=1, and true for n=k leads to true for n=k+1, so true for all n (R1).

(d) S_n\le2-\dfrac1n<2 (A1).

(e) \dfrac1{k-1}-\dfrac1k=\dfrac1{k(k-1)} (M1), which exceeds \dfrac1{k^2} because k(k-1)<k^2 (A1). Then S_n<1+\sum_{k=2}^{n}\left(\dfrac1{k-1}-\dfrac1k\right) (M1) =1+\left(1-\dfrac1n\right)=2-\dfrac1n (A1).

(f) S_m-S_n=\sum_{k=n+1}^{m}\dfrac1{k^2}<\sum_{k=n+1}^{m}\left(\dfrac1{k-1}-\dfrac1k\right) (M1) =\dfrac1n-\dfrac1m<\dfrac1n (A1). Letting m\to\infty gives L-S_n\le\dfrac1n. With n=4: S_4<L\le S_4+\dfrac14 (M1), that is 1.4236\ldots<L\le1.6736\ldots, so a=1.42 and b=1.68 (A1).

(g) Need \dfrac1n<0.001 (M1), so n>1000 and the least value is n=1001 (A1).

Final answer

Bounding a sum of reciprocal squares. (a) 1,\,\frac54,\,\frac{49}{36},\,\frac{205}{144}. (c) S_n\le2-\frac1n. (d) S_n<2. (f) L-S_n\le\frac1n; 1.42<L\le1.68. (g) n=1001.

Investigation 7

[24 marks]

This question asks you to study a sequence of fractions that approaches \sqrt2 and to bound its error.

The sequence u_n is defined by u_0=1 and u_{n+1}=\dfrac{u_n+2}{u_n+1}.

(a) Find u_1, u_2, u_3 and u_4 as fractions.

[2]

(b) Show that if u_n approaches a limit L>0, then L=\sqrt2.

[2]

Write u_n=\dfrac{p_n}{q_n}, where p_0=q_0=1, p_{n+1}=p_n+2q_n and q_{n+1}=p_n+q_n.

(c) Prove by induction that p_n^2-2q_n^2=(-1)^{n+1} for all n\in\mathbb{N}.

[6]

(d) Hence show that \left|u_n-\sqrt2\right|=\dfrac1{q_n^2\left(u_n+\sqrt2\right)}.

[4]

(e) Explain why u_n is alternately below and above \sqrt2.

[2]

(f) Show that q_{n+1}>2q_n for n\ge1. Show also that \left|u_n-\sqrt2\right|<\dfrac1{2q_n^2} for n\ge1.

[4]

(g) Find the least value of n for which \left|u_n-\sqrt2\right|<10^{-6}.

[4]

Show solutionHide solution

(a) u_1=\dfrac32 (M1), u_2=\dfrac75, u_3=\dfrac{17}{12}, u_4=\dfrac{41}{29} (A1).

(b) L=\dfrac{L+2}{L+1} (M1), so L^2+L=L+2, L^2=2 and, as L>0, L=\sqrt2 (A1).

(c) n=0: 1-2=-1=(-1)^1 (A1). Assume p_k^2-2q_k^2=(-1)^{k+1} (M1). Then p_{k+1}^2-2q_{k+1}^2=(p_k+2q_k)^2-2(p_k+q_k)^2 (M1) =-p_k^2+2q_k^2=-(-1)^{k+1} (A1) =(-1)^{k+2} (A1). True for n=0, and true for n=k leads to true for n=k+1, so true for all n\in\mathbb{N} (R1).

(d) u_n-\sqrt2=\dfrac{p_n-\sqrt2q_n}{q_n}=\dfrac{p_n^2-2q_n^2}{q_n\left(p_n+\sqrt2q_n\right)} (M1 A1). By (c) the numerator has modulus 1 (A1). Dividing top and bottom of the denominator by q_n gives q_n^2\left(u_n+\sqrt2\right) (A1).

(e) u_n-\sqrt2 has the sign of p_n^2-2q_n^2=(-1)^{n+1} (M1), because p_n+\sqrt2q_n>0. This is positive for odd n and negative for even n (A1).

(f) u_n=1+\dfrac1{u_{n-1}+1}>1 for n\ge1, since all terms are positive, so p_n>q_n (M1). Then q_{n+1}=p_n+q_n>2q_n (A1). By (d), and since u_n+\sqrt2>1+\sqrt2>2 (M1), \left|u_n-\sqrt2\right|<\dfrac1{2q_n^2} (A1).

(g) \dfrac1{2q_n^2}<10^{-6} needs q_n>707.1 (M1). From q_{n+1}=p_n+q_n the values are q_6=169, q_7=408, q_8=985 (A1). So n=8 is enough (A1). For n=7 the exact error is \dfrac1{408^2\left(\frac{577}{408}+\sqrt2\right)}=2.12\times10^{-6}, which is too large, so the least value is n=8 (A1).

Final answer

Closing in on root two. (a) \frac32,\,\frac75,\,\frac{17}{12},\,\frac{41}{29}. (c) p_{k+1}^2-2q_{k+1}^2=-(p_k^2-2q_k^2). (e) sign of (-1)^{n+1}. (f) p_n>q_n and u_n+\sqrt2>2. (g) n=8.

Investigation 8

[25 marks]

This question asks you to find closed forms for sequences defined by a two-step recurrence, and to prove them.

The sequence u_n is defined by u_0=1, u_1=4 and u_{n+2}=4u_{n+1}-4u_n for n\ge0.

(a) Find u_2, u_3, u_4 and u_5.

[2]

(b) Find \dfrac{u_n}{2^n} for n=0,\dots,5, and hence suggest a formula for u_n.

[3]

(c) Prove your formula by induction.

[6]

(d) Show that v_n=(A+Bn)\,2^n satisfies v_{n+2}=4v_{n+1}-4v_n for all constants A and B.

[3]

(e) A second sequence w_n has w_0=2, w_1=2 and the same recurrence. Find w_2 to w_5, and find and prove a formula for w_n.

[5]

(f) Prove that u_0+u_1+\dots+u_n=n\times2^{n+1}+1 for all n\in\mathbb{N}.

[4]

(g) Find the least value of n for which u_n>10^6.

[2]

Show solutionHide solution

(a) u_2=16-4=12 (M1), u_3=48-16=32, u_4=128-48=80, u_5=320-128=192 (A1).

(b) u_n/2^n is 1,\,2,\,3,\,4,\,5,\,6 (M1 A1), so u_n=(n+1)\,2^n (A1).

(c) n=0: 1\times1=1 and n=1: 2\times2=4 (A1). Assume true for n=k-1 and n=k, where k\ge1 (M1). Then u_{k+1}=4u_k-4u_{k-1} (M1) =4(k+1)2^k-4k\,2^{k-1} (A1) =(k+1)2^{k+2}-k\,2^{k+1}=2^{k+1}(2k+2-k)=(k+2)\,2^{k+1} (A1), the formula with n=k+1. True for n=0,1, and if true for n=k-1 and n=k then true for n=k+1, so true for all n\in\mathbb{N} (R1).

(d) 4v_{n+1}-4v_n=4\left(A+B(n+1)\right)2^{n+1}-4(A+Bn)2^n (M1) =2^{n+2}\left[2\left(A+Bn+B\right)-(A+Bn)\right] (M1) =2^{n+2}\left(A+B(n+2)\right)=v_{n+2} (A1).

(e) w_2=8-8=0 (M1), w_3=0-8=-8, w_4=-32-0=-32, w_5=-128+32=-96 (A1). By (d) the form (A+Bn)2^n satisfies the recurrence; w_0=2 gives A=2 and w_1=2 gives 2(2+B)=2, so B=-1 (M1): w_n=(2-n)\,2^n (A1). The recurrence fixes every term from the first two, and this formula satisfies the recurrence and matches w_0 and w_1, so it equals w_n for all n (R1).

(f) n=0: u_0=1=0+1 (A1). Assume \sum_{i=0}^{k}u_i=k\,2^{k+1}+1; then the sum to k+1 is k\,2^{k+1}+1+(k+2)2^{k+1} (M1) =(2k+2)2^{k+1}+1=(k+1)2^{k+2}+1 (A1). True for n=0, and true for n=k leads to true for n=k+1, so true for all n (R1).

(g) Solve (n+1)2^n>10^6 with a table (M1): u_{15}=16\times32768=524\,288 and u_{16}=17\times65\,536=1\,114\,112, so n=16 (A1).

Final answer

A recurrence with a repeated root. (a) 12,\,32,\,80,\,192. (b) u_n=(n+1)2^n. (e) 0,\,-8,\,-32,\,-96; w_n=(2-n)2^n. (g) n=16.

Going further

Beyond the syllabus: the worked examples and investigations of the chapter's Going further pages.

Investigation

[25 marks]

Worked investigation 1: Tiling a path.

This question asks you to count the ways of paving a path and to prove a formula for the count. A garden path is 2 units wide and n units long. It is paved with rectangular slabs measuring 1 unit by 2 units, which may be placed either way round, and square slabs measuring 2 units by 2 units. Let t_n be the number of different ways of paving the path.

(a) Show that t_1=1 and t_2=3, drawing each arrangement.

[3]

(b) By considering the slabs at the right-hand end of the path, explain why t_n=t_{n-1}+2t_{n-2} for n\ge3.

[4]

(c) Find t_3, t_4, t_5 and t_6.

[2]

(d) Show that t_n is close to \dfrac{2^{n+1}}{3} for n=1,2,\dots,6, and hence suggest an exact formula for t_n.

[3]

(e) Prove your formula by mathematical induction.

[6]

(f) Prove that t_n is odd for every n\in\mathbb{Z}^+.

[3]

(g) Find \displaystyle\lim_{n\to\infty}\dfrac{t_{n+1}}{t_n} and interpret it for long paths.

[2]

(h) A path 2 units wide and 12 units long is paved at random, every arrangement being equally likely. Find the probability that it contains no square slab.

[2]

Show solutionHide solution

(a) t_1=1: the path is 1 unit long, so the only slab that fits is one rectangle standing across it (A1); t_2=3: two rectangles standing across; two rectangles lying along, one above the other; one square (A1); No other arrangement exists: a rectangle lying along the path forces a second one beside it, because a single unit of width cannot be filled otherwise (R1).

(b) Look at the right-hand end of a path of length n\ge3 (M1); Case 1: a rectangle stands across the last unit. The rest is a path of length n-1: t_{n-1} ways (A1); Case 2: the last two units are covered by one square or by two rectangles lying along. The rest is a path of length n-2: 2\times t_{n-2} ways (A1); The cases are exhaustive and cannot overlap, so t_n=t_{n-1}+2t_{n-2} (R1).

(c) t_3=t_2+2t_1=3+2=5 and t_4=5+2\times3=11 (M1); t_5=11+2\times5=21 and t_6=21+2\times11=43 (A1).

(d) \dfrac{2^{n+1}}{3} for n=1,\dots,6: 1.33,\ 2.67,\ 5.33,\ 10.67,\ 21.33,\ 42.67 (M1); t_n-\dfrac{2^{n+1}}{3}=-\dfrac13,\ +\dfrac13,\ -\dfrac13,\dots: the difference alternates in sign (A1); Conjecture: t_n=\dfrac{2^{n+1}+(-1)^n}{3} (A1).

(e) Base cases: n=1: \dfrac{4-1}{3}=1; n=2: \dfrac{8+1}{3}=3. Both true (A1); Assume the formula is true for n=k and for n=k-1, where k\ge2 (M1); t_{k+1}=t_k+2t_{k-1} (M1); =\dfrac{2^{k+1}+(-1)^k}{3}+\dfrac{2\left(2^{k}+(-1)^{k-1}\right)}{3} (A1); =\dfrac{2^{k+1}+2^{k+1}+(-1)^k-2(-1)^k}{3}=\dfrac{2^{k+2}+(-1)^{k+1}}{3} (A1); True for n=1,2; and if true for n=k-1 and n=k then true for n=k+1. So true for all n\in\mathbb{Z}^+ by induction (R1).

(f) t_1=1 and t_2=3 are odd (A1); If t_{k-1} and t_k are odd, then t_{k+1}=t_k+2t_{k-1} is odd plus even (M1); so t_{k+1} is odd; true for all n by induction (R1).

(g) Divide top and bottom by 2^{n+1}: \dfrac{t_{n+1}}{t_n}=\dfrac{2+(-1)^{n+1}/2^{n+1}}{1+(-1)^n/2^{n+1}}\to2 (A1); Each extra unit of length roughly doubles the number of ways to pave the path (A1).

(h) With no square, the end is a rectangle across or a pair along: s_n=s_{n-1}+s_{n-2}, s_1=1, s_2=2, so s_{12}=233 and t_{12}=\dfrac{2^{13}+1}{3}=2731 (M1); Probability =\dfrac{233}{2731}=0.0853 (A1).

Final answer

(a) three arrangements; (b) proof; (c) 5,\,11,\,21,\,43; (d) t_n=\dfrac{2^{n+1}+(-1)^n}{3}; (e) proof; (f) proof; (g) 2; (h) 0.0853.

Investigation

[23 marks]

Worked investigation 2: Factorial sums.

This question asks you to find and prove closed forms for two sums that involve factorials. Let S_n=\displaystyle\sum_{k=1}^{n}k\times k! and T_n=\displaystyle\sum_{k=1}^{n}\dfrac{k}{(k+1)!}, for n\in\mathbb{Z}^+.

(a) Find S_1, S_2, S_3, S_4 and S_5.

[2]

(b) Suggest an expression for S_n in terms of n.

[2]

(c) Prove your suggestion by mathematical induction.

[5]

(d) Show that k\times k!=(k+1)!-k!, and use this to give a second proof of your result in (b).

[3]

(e) Find T_1, T_2, T_3 and T_4 as fractions, and suggest an expression for T_n.

[3]

(f) Show that \dfrac{k}{(k+1)!}=\dfrac1{k!}-\dfrac1{(k+1)!}, and hence prove your suggestion in (e).

[3]

(g) Find \displaystyle\lim_{n\to\infty}T_n.

[1]

(h) Show that S_n+1 is divisible by every integer from 1 to n+1.

[2]

(i) Find the final digit of S_n for n\ge4, justifying your answer.

[2]

Show solutionHide solution

(a) k\times k! for k=1,\dots,5: 1,\ 4,\ 18,\ 96,\ 600 (M1); S_1=1,\ S_2=5,\ S_3=23,\ S_4=119,\ S_5=719 (A1).

(b) Each value is one less than a factorial: 2!-1,\ 3!-1,\ 4!-1,\ 5!-1,\ 6!-1 (M1); S_n=(n+1)!-1 (A1).

(c) n=1: S_1=1\times1!=1 and (1+1)!-1=1. True (A1); Assume S_k=(k+1)!-1 for some k\in\mathbb{Z}^+ (M1); S_{k+1}=S_k+(k+1)\times(k+1)! (M1); =(k+1)!-1+(k+1)\times(k+1)!=(k+1)!\,(1+k+1)-1=(k+2)!-1 (A1); This is the formula with n=k+1. The base case n=1 holds, and n=k holding leads to n=k+1 holding, so the statement holds for all n\in\mathbb{Z}^+ by induction (R1).

(d) k\times k!=\bigl((k+1)-1\bigr)k!=(k+1)k!-k! (M1); =(k+1)!-k! (AG); S_n=\sum_{k=1}^{n}\bigl[(k+1)!-k!\bigr]=(2!-1!)+(3!-2!)+\dots+\bigl((n+1)!-n!\bigr) (M1); =(n+1)!-1!=(n+1)!-1 (A1).

(e) T_1=\dfrac12, T_2=\dfrac12+\dfrac26=\dfrac56 (M1); T_3=\dfrac56+\dfrac3{24}=\dfrac{23}{24}, T_4=\dfrac{23}{24}+\dfrac4{120}=\dfrac{119}{120} (A1); The denominators are 2!,3!,4!,5! and each fraction is 1-\dfrac1{(n+1)!}: T_n=1-\dfrac1{(n+1)!} (A1).

(f) \dfrac{k}{(k+1)!}=\dfrac{(k+1)-1}{(k+1)!}=\dfrac{k+1}{(k+1)!}-\dfrac1{(k+1)!} (M1); =\dfrac1{k!}-\dfrac1{(k+1)!} (AG); T_n=\Bigl(\dfrac1{1!}-\dfrac1{2!}\Bigr)+\Bigl(\dfrac1{2!}-\dfrac1{3!}\Bigr)+\dots+\Bigl(\dfrac1{n!}-\dfrac1{(n+1)!}\Bigr)=1-\dfrac1{(n+1)!} (M1); The result is the suggestion in (e) (A1).

(g) \dfrac1{(n+1)!}\to0, so T_n\to1 (A1).

(h) By (b), S_n+1=(n+1)! (M1); (n+1)!=1\times2\times\dots\times(n+1), so every integer from 1 to n+1 is a factor (R1).

(i) For n\ge4, n+1\ge5, so (n+1)! has factors 2 and 5, hence is a multiple of 10 (M1); S_n=(n+1)!-1 ends in 9 (A1).

Final answer

(a) 1,\,5,\,23,\,119,\,719; (b) S_n=(n+1)!-1; (c) proof; (d) proof; (e) \tfrac12,\tfrac56,\tfrac{23}{24},\tfrac{119}{120}; T_n=1-\tfrac1{(n+1)!}; (f) proof; (g) 1; (h) proof; (i) 9.

From the book

Photon Guidebook: Mathematics HL Paper 3 for the IB Diploma

Chapter 4 teaches sequences, recurrences and proof by induction: how the IB builds this kind of Paper 3 question, the techniques, marked worked investigations, and practice investigations like these.

About the book