Question

Prove by the principle of mathematical induction that n < 2ⁿ for all n∈N.

Answer 1

Let the statement T(n) = n < 2ⁿ. 

Basic Step: For n = 1, 1 < 2¹ 

⇒ T(1) is true. 

Induction Step: 

Let T(k) be true ⇒ k< 2^k for all k∈N. 

k < 2^k ⇒ 2k < 2.2^k 

⇒ 2k < 2^{k + 1} ⇒ (k + k) < 2^{k + 1} 

⇒ (k + 1) \(\leq\) (k + k) < 2^{k + 1} (\(\because\) k∈N ⇒ k \(\geq\) 1) 

⇒ (k + 1) < 2^{k + 1} 

⇒ T (k + 1) is true, whenever T(k) is true. 

∴ T(n) is true ∀ n∈N.