Answer to Question #121428 in Discrete Mathematics for Montsuoe

Question

Let n be a natural number. Use mathematical induction to prove that
4
n−1 > n2
for all n ≥ 3.

Answer 1

Let the statement $P(n) = 4^{n−1} > n^2$

Now, $4^{3-1} = 4^2 = 16 > 3^2$ , So $P(n)$ is true for $n = 3$ .

Let $P(n)$ is true for $n = k$ $\implies 4^{k-1} > k^2$ .

Now, prove $P(n)$ is true for $n = k+1.$

$4^{(k+1)-1} = 4 \times 4^{k-1} > 4 \times k^2 > k^2 + 2k^2+k^2 > k^2 + 2k +1$ because $k \geq 3$ .

Hence, $4^{(k+1)-1} > (k+1)^2$

Hence, using Principal of Mathematical Induction, $4^{n-1}>n^2$ for all $n\geq 3$ .