IBDP Maths analysis and approaches Topic: AHL 1.15 Proof by mathematical induction HL Paper 1

Question

Consider integers a and b such that a 2 + b2 is exactly divisible by 4. Prove by contradiction that a and b cannot both be odd.

▶️Answer/Explanation

Ans:

Assume that a and b are both odd.

Note: Award M0 for statements such as “let a and b be both odd”.
Note: Subsequent marks after this M1 are independent of this mark and can be awarded.

Then a = 2m + 1 and b = 2n + 1

a2 + b2 ≡ (2m + 1)2 + (2n + 1)2

= 4m2 + 4m + 1 + 4n2 + 4n + 1

= 4 (m2 + m + n2 + n) + 2

(4(m2 + m + n2 + n) is always divisible by 4) but 2 is not divisible by 4. (or equivalent) 

⇒a2 + b2 is not divisible by 4, a contradiction. (or equivalent)

hence a and b cannot both be odd.

Note: Award a maximum of M1A0A0(A0)R1R1 for considering identical or two consecutive odd numbers for a and b.

Question

Prove by contradiction that the equation 2x3 + 6x + 1 = 0 has no integer roots.

▶️Answer/Explanation

Ans:

METHOD 1 (rearranging the equation)
assume there exists some α∈ Z such that 2α3 + 6α + 1 = 0

Note: Award M1 for equivalent statements such as ‘assume that α is an integer root of  \(2\alpha ^{3} + 6\alpha +1 = 0′.\) Condone the use of x throughout the proof. Award Award M1 for an assumption involving for an assumption involving  \(\alpha ^{3} + 3\alpha +\frac{1}{2} = 0.\)

Note: Award M0 for statements such as “let’s consider the equation has integer roots…” ,“let α ∈ Z  be a root of 2α3 + 6α + 1 = 0 ….”

Note: Subsequent marks after this M1 are independent of this M1 and can be awarded.

attempts to rearrange their equation into a suitable form

EITHER

Question

Consider integers a and b such that a 2 + b2 is exactly divisible by 4. Prove by contradiction that a and b cannot both be odd.

Answer/Explanation

Ans:

Assume that a and b are both odd.

Note: Award M0 for statements such as “let a and b be both odd”.
Note: Subsequent marks after this M1 are independent of this mark and can be awarded.

Then a = 2m + 1 and b = 2n + 1

a2 + b2 ≡ (2m + 1)2 + (2n + 1)2

= 4m2 + 4m + 1 + 4n2 + 4n + 1

= 4 (m2 + m + n2 + n) + 2

(4(m2 + m + n2 + n) is always divisible by 4) but 2 is not divisible by 4. (or equivalent) 

⇒a2 + b2 is not divisible by 4, a contradiction. (or equivalent)

hence a and b cannot both be odd.

Note: Award a maximum of M1A0A0(A0)R1R1 for considering identical or two consecutive odd numbers for a and b.

Question

Let (1021)n denote a number expressed in number base n .

Use mathematical induction to prove that (1021)n is not divisible by 3 , for n ≥ 3 . [7]

▶️Answer/Explanation

Ans:

 ( 1021)n =  n3 + 2n + 1

when n = 3, ( 1021)n  = 34 so the proposition is true for n = 3

assume the proposition is true for n = k, ie, k3 + 2k + 1 is not divisible  by 3

for n = k + 1, consider

\((k+1)^3 +2(k+1)+1=k^3 +3k^2+3k+1+2(k+1)+1\)

\(=(k^3+2k+1)+(3k^2+3k+3)\)

first term is not divisible by 3 by assumption and second term is divisible by 3,

hence the sum of the 2 terms is not divisible by 3

therefore true for  \(n=k => \) true for    \(n=k+1\)  and since true for \(n=3\)
the proposition is true for \(n\geqslant 3\)

Question

Let f (x) = \(\sqrt{1+x}\)  for x > -1 .

(a)        Show that f (x)′′ = − \(\frac{1}{\sqrt[4]{(1+x)}^{3}}\) [3]

▶️Answer/Explanation

Ans: attempt to use the chain rule

\(f'(x)= \frac{1}{2}(1+x)^{\frac{-1}{2}}\)

f”(x)= – \(\frac{1}{\sqrt[4]{(1+x)^3}}\)

(b) Use mathematical induction to prove that f(n) (x) = \((-\frac{1}{4})^{n-1}\frac{(2n-3)!}{(n-2)!}(1+x)^{\frac{1}{2}-n}\)

for  \(n\in \mathbb{Z}\;,n\geqslant 2\) [9]

Let g (x) = emx , m \(\in \mathbb{Q}\)

Consider the function h defined by h (x) = f (x) x g (x) for x > -1 .

It is given that the x2 term in the Maclaurin series for h (x) has a coefficient of  \(\frac{7}{4}\)

▶️Answer/Explanation

Ans:

(c) Find the possible values of m .       [8]

▶️Answer/Explanation

Ans

Question

Consider the function \({f_n}(x) = (\cos 2x)(\cos 4x) \ldots (\cos {2^n}x),{\text{ }}n \in {\mathbb{Z}^ + }\).

a. Determine whether \({f_n}\) is an odd or even function, justifying your answer.[2]

▶️Answer/Explanation

Ans:

even function     A1

since \(\cos kx = \cos ( – kx)\) and \({f_n}(x)\) is a product of even functions     R1

OR

even function     A1

since \((\cos 2x)(\cos 4x) \ldots  = \left( {\cos ( – 2x)} \right)\left( {\cos ( – 4x)} \right) \ldots \)     R1

Note:     Do not award A0R1. [2 marks]

b. By using mathematical induction, prove that

\({f_n}(x) = \frac{{\sin {2^{n + 1}}x}}{{{2^n}\sin 2x}},{\text{ }}x \ne \frac{{m\pi }}{2}\) where \(m \in \mathbb{Z}\).[8]

▶️Answer/Explanation

Ans:

consider the case \(n = 1\)

\(\frac{{\sin 4x}}{{2\sin 2x}} = \frac{{2\sin 2x\cos 2x}}{{2\sin 2x}} = \cos 2x\)     M1

hence true for \(n = 1\)     R1

assume true for \(n = k\), ie, \((\cos 2x)(\cos 4x) \ldots (\cos {2^k}x) = \frac{{\sin {2^{k + 1}}x}}{{{2^k}\sin 2x}}\)     M1

Note:     Do not award M1 for “let \(n = k\)” or “assume \(n = k\)” or equivalent.

consider \(n = k + 1\):

\({f_{k + 1}}(x) = {f_k}(x)(\cos {2^{k + 1}}x)\)     (M1)

\( = \frac{{\sin {2^{k + 1}}x}}{{{2^k}\sin 2x}}\cos {2^{k + 1}}x\)     A1

\( = \frac{{2\sin {2^{k + 1}}x\cos {2^{k + 1}}x}}{{{2^{k + 1}}\sin 2x}}\)     A1

\( = \frac{{\sin {2^{k + 2}}x}}{{{2^{k + 1}}\sin 2x}}\)     A1

so \(n = 1\) true and \(n = k\) true \( \Rightarrow n = k + 1\) true. Hence true for all \(n \in {\mathbb{Z}^ + }\)     R1

Note:     To obtain the final R1, all the previous M marks must have been awarded.

[8 marks]

c. Hence or otherwise, find an expression for the derivative of \({f_n}(x)\) with respect to \(x\).[3]
▶️Answer/Explanation

Ans:

attempt to use \(f’ = \frac{{vu’ – uv’}}{{{v^2}}}\) (or correct product rule)     M1

\({f’_n}(x) = \frac{{({2^n}\sin 2x)({2^{n + 1}}\cos {2^{n + 1}}x) – (\sin {2^{n + 1}}x)({2^{n + 1}}\cos 2x)}}{{{{({2^n}\sin 2x)}^2}}}\)     A1A1

Note:     Award A1 for correct numerator and A1 for correct denominator.

[3 marks]

d. Show that, for \(n > 1\), the equation of the tangent to the curve \(y = {f_n}(x)\) at \(x = \frac{\pi }{4}\) is \(4x – 2y – \pi  = 0\).[8]
▶️Answer/Explanation

Ans:

\({f’_n}\left( {\frac{\pi }{4}} \right) = \frac{{\left( {{2^n}\sin \frac{\pi }{2}} \right)\left( {{2^{n + 1}}\cos {2^{n + 1}}\frac{\pi }{4}} \right) – \left( {\sin {2^{n + 1}}\frac{\pi }{4}} \right)\left( {{2^{n + 1}}\cos \frac{\pi }{2}} \right)}}{{{{\left( {{2^n}\sin \frac{\pi }{2}} \right)}^2}}}\)     (M1)(A1)

\({f’_n}\left( {\frac{\pi }{4}} \right) = \frac{{({2^n})\left( {{2^{n + 1}}\cos {2^{n + 1}}\frac{\pi }{4}} \right)}}{{{{({2^n})}^2}}}\)     (A1)

\( = 2\cos {2^{n + 1}}\frac{\pi }{4}{\text{ }}( = 2\cos {2^{n – 1}}\pi )\)     A1

\({f’_n}\left( {\frac{\pi }{4}} \right) = 2\)     A1

\({f_n}\left( {\frac{\pi }{4}} \right) = 0\)     A1

Note:     This A mark is independent from the previous marks.

\(y = 2\left( {x – \frac{\pi }{4}} \right)\)     M1A1

\(4x – 2y – \pi  = 0\)     AG [8 marks]

 

Question

Consider a function f , defined by \(f(x) = \frac{x}{{2 – x}}{\text{ for }}0 \leqslant x \leqslant 1\) .

a. Find an expression for \((f \circ f)(x)\) .  [3]

▶️Answer/Explanation

Ans:

\((f \circ f)(x) = f\left( {\frac{x}{{2 – x}}} \right) = \frac{{\frac{x}{{2 – x}}}}{{2 – \frac{x}{{2 – x}}}}\)     M1A1

\((f \circ f)(x) = \frac{x}{{4 – 3x}}\)     A1

[3 marks]

b. Let \({F_n}(x) = \frac{x}{{{2^n} – ({2^n} – 1)x}}\), where \(0 \leqslant x \leqslant 1\).

Use mathematical induction to show that for any \(n \in {\mathbb{Z}^ + }\)

\[\underbrace {(f \circ f \circ … \circ f)}_{n{\text{ times}}}(x) = {F_n}(x)\] .[8]

▶️Answer/Explanation

Ans:

\(P(n):\underbrace {(f \circ f \circ … \circ f)}_{n{\text{ times}}}(x) = {F_n}(x)\)

\(P(1):{\text{ }}f(x) = {F_1}(x)\)

\(LHS = f(x) = \frac{x}{{2 – x}}{\text{ and }}RHS = {F_1}(x) = \frac{x}{{{2^1} – ({2^1} – 1)x}} = \frac{x}{{2 – x}}\)     A1A1

\(\therefore P(1){\text{ true}}\)

assume that P(k) is true, i.e., \(\underbrace {(f \circ f \circ … \circ f)}_{{\text{k times}}}(x) = {F_k}(x)\)     M1

consider \(P(k + 1)\)

EITHER

\(\underbrace {(f \circ f \circ … \circ f)}_{{\text{k}} + 1{\text{ times}}}(x) = \left( {f \circ \underbrace {f \circ f \circ … \circ f}_{{\text{k times}}}} \right)(x) = f\left( {{F_k}(x)} \right)\)     (M1)

\( = f\left( {\frac{x}{{{2^k} – ({2^k} – 1)x}}} \right) = \frac{{\frac{x}{{{2^k} – ({2^k} – 1)x}}}}{{2 – \frac{x}{{{2^k} – ({2^k} – 1)x}}}}\)     A1

\( = \frac{x}{{2\left( {{2^k} – ({2^k} – 1)x} \right) – x}} = \frac{x}{{{2^{k + 1}} – ({2^{k + 1}} – 2)x – x}}\)     A1

OR

\(\underbrace {(f \circ f \circ … \circ f)}_{{\text{k}} + 1{\text{ times}}}(x) = \left( {f \circ \underbrace {f \circ f \circ … \circ f}_{{\text{k times}}}} \right)(x) = {F_k}(f(x))\)     (M1)

\( = {F_k}\left( {\frac{x}{{2 – x}}} \right) = \frac{{\frac{x}{{2 – x}}}}{{{2^k} – ({2^k} – 1)\frac{x}{{2 – x}}}}\)     A1

\( = \frac{x}{{{2^{k + 1}} – {2^k}x – {2^k}x + x}}\)     A1

THEN

\( = \frac{x}{{{2^{k + 1}} – ({2^{k + 1}} – 1)x}} = {F_{k + 1}}(x)\)     A1

P(k) true implies P(k + 1) true, P(1) true so P(n) true for all \(n \in {\mathbb{Z}^ + }\)     R1

[8 marks]

c. Show that \({F_{ – n}}(x)\) is an expression for the inverse of \({F_n}\) .[6]

▶️Answer/Explanation

Ans:

METHOD 1

\(x = \frac{y}{{{2^n} – ({2^n} – 1)y}} \Rightarrow {2^n}x – ({2^n} – 1)xy = y\)     M1A1

\( \Rightarrow {2^n}x = \left( {({2^n} – 1)x + 1} \right)y \Rightarrow y = \frac{{{2^n}x}}{{({2^n} – 1)x + 1}}\)     A1

\(F_n^{ – 1}(x) = \frac{{{2^n}x}}{{({2^n} – 1)x + 1}}\)     A1

\(F_n^{ – 1}(x) = \frac{x}{{\frac{{{2^n} – 1}}{{{2^n}}}x + \frac{1}{{{2^n}}}}}\)     M1

\(F_n^{ – 1}(x) = \frac{x}{{(1 – {2^{ – n}})x + {2^{ – n}}}}\)     A1

\(F_n^{ – 1}(x) = \frac{x}{{{2^{ – n}} – ({2^{ – n}} – 1)x}}\)     AG

METHOD 2

attempt \({F_{ – n}}\left( {{F_n}(x)} \right)\)     M1

\( = {F_{ – n}}\left( {\frac{x}{{{2^n} – ({2^n} – 1)x}}} \right) = \frac{{\frac{x}{{{2^n} – ({2^n} – 1)x}}}}{{{2^{ – n}} – ({2^{ – n}} – 1)\frac{x}{{{2^n} – ({2^n} – 1)x}}}}\)     A1A1

\( = \frac{x}{{{2^{ – n}}({2^n} – ({2^n} – 1)x) – ({2^{ – n}} – 1)x}}\)     A1A1

Note: Award A1 marks for numerators and denominators.

 

\( = \frac{x}{1} = x\)     A1AG

METHOD 3

attempt \({F_n}\left( {{F_{ – n}}(x)} \right)\)     M1

\( = {F_n}\left( {\frac{x}{{{2^{ – n}} – ({2^{ – n}} – 1)x}}} \right) = \frac{{\frac{x}{{{2^{ – n}} – ({2^{ – n}} – 1)x}}}}{{{2^n} – ({2^n} – 1)\frac{x}{{{2^{ – n}} – ({2^{ – n}} – 1)x}}}}\)     A1A1

\( = \frac{x}{{{2^n}({2^{ – n}} – ({2^{ – n}} – 1)x) – ({2^n} – 1)x}}\)     A1A1

Note: Award A1 marks for numerators and denominators.

 

\( = \frac{x}{1} = x\)     A1AG

[6 marks]

d. (i)     State \({F_n}(0){\text{ and }}{F_n}(1)\) .

(ii)     Show that \({F_n}(x) < x\) , given 0 < x < 1, \(n \in {\mathbb{Z}^ + }\) .

(iii)     For \(n \in {\mathbb{Z}^ + }\) , let \({A_n}\) be the area of the region enclosed by the graph of \(F_n^{ – 1}\) , the x-axis and the line x = 1. Find the area \({B_n}\) of the region enclosed by \({F_n}\) and \(F_n^{ – 1}\) in terms of \({A_n}\) .[6]

▶️Answer/Explanation

Ans:

(i)     \({F_n}(0) = 0,{\text{ }}{F_n}(1) = 1\)     A1

 

(ii)     METHOD 1

\({2^n} – ({2^n} – 1)x – 1 = ({2^n} – 1)(1 – x)\)     (M1)

\( > 0{\text{ if }}0 < x < 1{\text{ and }}n \in {\mathbb{Z}^ + }\)     A1

so \({2^n} – ({2^n} – 1)x > 1{\text{ and }}{F_n}(x) = \frac{x}{{{2^n} – ({2^n} – 1)x}} < \frac{x}{1}( < x)\)     R1

\({F_n}(x) = \frac{x}{{{2^n} – ({2^n} – 1)x}} < x{\text{ for }}0 < x < 1{\text{ and }}n \in {\mathbb{Z}^ + }\)     AG

METHOD 2

\(\frac{x}{{{2^n} – ({2^n} – 1)x}} < x \Leftrightarrow {2^n} – ({2^n} – 1)x > 1\)     (M1)

\( \Leftrightarrow ({2^n} – 1)x < {2^n} – 1\)     A1

\( \Leftrightarrow x < \frac{{{2^n} – 1}}{{{2^n} – 1}} = 1\) true in the interval \(\left] {0,{\text{ }}1} \right[\)     R1

 

(iii)     \({B_n} = 2\left( {{A_n} – \frac{1}{2}} \right){\text{ }}( = 2{A_n} – 1)\)     (M1)A1

[6 marks]

 

Question

Use mathematical induction to prove that 5n + 9n+ 2 is divisible by 4, for n ∈ \(\epsilon \mathbb{Z}^{+}\).

▶️Answer/Explanation

Ans
Let f(n) = 5n + 9n + 2 and let Pn be the proposition that f(n) is divisible by 4.
Then f(1) = 16. So P1 is true
Let Pn be true for n = k ie f(k) is divisible by 4
Consider \(f(k+1)=5^{k+1}+9^{k+1}+2=5^k(4+1)+9^k(8+1)+2\)
=\(f(k)+4(5^k+2\chi9^k)\)
Both terms are divisible by 4 so f(k+1) is divisible by 4.
Pk true ⇒ Pk+l true
Since P1 is true, Pn is proved true by mathematical induction for n ∈ \(\mathbb{Z}^+\).

Scroll to Top