Exercises: Induction proofs of inequalities

Let $P(n)$ be the statement $2^n \geq n + 1$.

1. a) Show that $P(1)$ and $P(2)$ are true.

1. b) Assuming $P(k)$ is true, prove that $P(k+1)$ is true.

Let $P(n)$ be the statement $n! > 2^n$.

1. a) Show that $P(4)$ is true.

1. b) Show that $P(3)$ is false.

1. c) Explain why the base case for a proof by induction must be $n = 4$.

Prove by induction that $3^n > 2n$ for all $n \in \mathbb{N}$.

Prove by induction that $n! > 2^n$ for all integers $n \geq 4$.

Prove by induction that $2^n \geq n^2$ for all integers $n \geq 4$. Check by direct calculation that the inequality fails for $n = 3$.

Prove by induction that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$, where $x > 0$.

Prove by induction that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$ and all real $x \geq -1$. Explain where in your proof the condition $x \geq -1$ is used. Hence show that $(0.99)^{50} \geq 0.5$.

Prove by induction that $\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \dots + \frac{1}{\sqrt{n}} \geq \sqrt{n}$ for all $n \in \mathbb{N}$.

1. a) Prove by induction that $2^n > n^3$ for all integers $n \geq 10$.

1. b) Find, with justification, the values of $n \in \mathbb{N}$ for which $2^n \leq n^3$.