Vrftsjtryk

Base case

$n=3$ - true

Inductive Step

Assume that for every $k geq 3$, $2^k>2k+1$ show that $P(k+1)$ holds, that is show that $2^{k+1} > 2k+3$

$2^{k+1} = 2^k*2 > (I.H) (2k+1)*2 > (k+2)*2 = 2k+4 > 2k+3$

Did I do this right? I am asking because I am not sure about $(2k+1)*2 > (k+2)*2$ step

$4k + 2 = 2k + 2 + 2k$. $k geq 3 implies 2k geq 6 > 2$ so you're right.

This is valid, you should just clean up and clarify some details a little.

Let $P(n)$ denote the proposition, $2^n > 2n + 1$, which we seek to prove for $n geq 3$.

Base Case: Here, we check $n=3$. $2^3 = 8 > 7 = 2(3) + 1$, so this holds.

Inductive Hypothesis: Suppose $P(k)$ for some $k > 3$. That is, we suppose that $2^k > 2k + 1$.

Induction: We seek to show $P(k+1)$ holds under the inductive hypothesis, that meaning we seek to show

$$2^{k+1} > 2(k+1) + 1 = 2k + 3$$

Then we note: by multiplying by $2$ on both sides of the assumption in the inductive hypothesis,

$$2 cdot 2^k = 2^{k+1} > 2 cdot (2k+1) = 4k + 2 $$

We want to show $4k+2 > 2k+4$: this is a detail crucial to your proof that is not immediately obvious (you yourself aren't sure). So note: like solving any other inequality,

$$4k+2 > 2k+4 Rightarrow 2k > 2 Rightarrow k > 1$$

Since our induction only cares about $n$ (and thus $k$) greater than or equal to $3$, then $4k+2 > 2k+4$ is perfectly valid for all the $k$ we care about. Thus, since trivially $2k+4 > 2k+3$, we have

$$2^{k+1} > 2 cdot (2k+1) = 4k + 2 > 2k+4 > 2k+3 = 2(k+1)+1$$

Having shown that $$2^{k+1} > 2(k+1)+1$$ we have shown that, for all $n geq 3$, $P(n)$ holds, i.e. for all $n geq 3, 2^n > 2n+1$.

Certain things are not transparent when expressed in symbols. In the formula ('sequence') $2^n$, every term is obtained by doubling the previous one: $2^{n+1} = 2times 2^n$. In the other formula we add 2 to the previous term: $2(n+1)+1 = 2n+1 + 2$.

Between a job which doubles your pay every month and one that adds 2 more dollars to your pay every month which one is preferable? (I assume you are not Perelman!)