IBDP Maths AHL 1.15 Proof by mathematical induction AA HL Paper 1- Exam Style Questions- New Syllabus

(a) Proving the inequality:

Start with left-hand side:
\( 1 + \log_2 n = \log_2 2 + \log_2 n \) (since \( 1 = \log_2 2 \))
\( = \log_2 (2n) \) (by log addition law)
Since \( n \in \mathbb{Z}^+ \), \( 2n \geq n + 1 \).
Because \( \log_2 x \) is an increasing function:
\( \log_2 (2n) \geq \log_2 (n + 1) \)
Thus \( 1 + \log_2 n \geq \log_2 (n + 1) \).

(b) Proof by induction:

Let \( P(n) \) be the statement: \( n > \log_2 n \) for \( n \in \mathbb{Z}^+ \).

Base case (\( n = 1 \)):

\( 1 > \log_2 1 = 0 \), which is true.
So \( P(1) \) holds.

Inductive hypothesis:

Assume \( P(k) \) is true for some \( k \in \mathbb{Z}^+ \):
\( k > \log_2 k \).

Inductive step:

Consider \( P(k+1) \): we need to show \( k+1 > \log_2 (k+1) \).
From the inductive hypothesis: \( k > \log_2 k \)
Add 1 to both sides: \( k + 1 > 1 + \log_2 k \)
From part (a): \( 1 + \log_2 k \geq \log_2 (k + 1) \)
Therefore \( k + 1 > \log_2 (k + 1) \).
So \( P(k+1) \) holds.

Conclusion:

Since \( P(1) \) is true, and \( P(k) \Rightarrow P(k+1) \) for all \( k \in \mathbb{Z}^+ \), by mathematical induction, \( P(n) \) is true for all \( n \in \mathbb{Z}^+ \).

Hence Anaya’s claim is valid.