basic mathematical induction problem

Question

1. Prove that for some $b \in \mathbb{N}$, $(\sqrt{2})^n > n$ for every $n \geq b$

Find such a $b \in \mathbb{N}$.

2. Prove that $\forall$$n \geq b$, $(\sqrt{2})^n > n$

How would I approach these problems and problems similar to these?

Answer 1

We can prove the thesis without induction.

Note that the derivative of $f(x) = 2^{x/2}$ is given by $f'(x)=\frac12 \log(2) 2^{x/2}$.

Then, $f'>0$ for all $x\ge 0$ and $f'>1$ for $x>\frac{2}{\log 2}\log(\frac{2}{\log 2})$.

Now, let's examine $2^{x/2}$ for values of $x\ge 4$. Note that at $x=4$, we have $2^{x/2}=2^2=4=x$.

Thus, for values for $x> 4$, $2^x>x$.

---

If one uses induction to prove this, then we first find a base case, say $n=1$.

Then $2^{n/2}=2^{1/2}>1=n$ is true.

So, let's hypothesize that for some $k$ that $2^{k/2}>k$.

Observe that $2^{(k+1)/2}=2^{1/2}2^{k/2}$.

But by hypothesis, we have $2^{k/2}>k$.

Thus, $2^{(k+1)/2}=2^{1/2}2^{k/2}>2^{1/2}k$.

This last expression, $2^{1/2}k$ will be bigger than $k+1$ if $(2^{1/2}-1)k>1$.

This is true when $k \ge 3$.

So, if $2^{k/2}>k$ and $k\ge 3$, then $2^{(k+1)/2}>k+1$ for all $k$.

Note that both of these conditions do not happen simultaneously until $k> 4$.