3. [8 marks] Induction. (a) [3 marks] Prove that 3 | 22n+ + 1 for all natural numbers n. (b) [5 marks] Prove that for all positive integers n, 2n - 1 1 X X . . X S 2n 3n HINT: You will find it difficult (likely impossible) to prove this directly. Consider proving a slightly stronger statement by making a small change to the expression inside the square root. Then, re- member to use what you prove to conclude the inequality in this question./