0
  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}$.

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

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

user123
  • 83
  • To begin, test some values of $n$ to get a sense which values work. Tell us what minimum value of $b$ you hypothesize. Then, if you must use induction, consider the relation $2^{n/2}/n > 1$. – Simon S Apr 14 '15 at 19:20
  • I ask the same question. Are you familiar with induction? – Sufyan Naeem Apr 14 '15 at 19:23
  • A base case could be $n=6$ for which we have $\sqrt 2^6=2^3=8>6$. Or if you like powers of $2$, use $n=20$ to have $2^{10}=1024>20$. – String Apr 14 '15 at 19:24

1 Answers1

2

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$.

Mark Viola
  • 179,405