0

Let p(n) be the mathematical statement: $2^n \leq 2^{n+1} - 2^{n-1} - 1$.

Base Case: When n = 1 we have $2^1 \leq 2^{1+1} - 2^{1-1} - 1$ which simplifies to $2 \leq 4$. So P(1) is correct.

Induction hypothesis: Assume that P(k) is correct for some integer k.

Induction step: We will now show that P(k + 1) is correct.

\begin{align} 2^{k+1} &= 2\cdot 2^{k}\tag{by definition}\\[0.5em] &\leq 2\cdot(2^{k+1}-2^{k-1}-1)\tag{by inductive hypothesis}\\[0.5em] &= 2^{k+2}-2^k-2\tag{expand}\\[0.5em] &\leq 2^{k+2}-2^k-1. \end{align}

Is this proof sufficient?

Seth Killian
  • 251
  • That looks great! I think the only thing I would change is in the induction hypothesis, you should say P(k) is correct for all natural numbers. Other than this, just make sure to state k,n, etc. are elements of the natural numbers. These are only minor details. – Jon Staggs Jun 20 '17 at 16:39
  • It is correct. I would prefer to see that you actually state the inductive hypothesis i.e. "Assume $2^k<2^{k+1} + 2^{k-1} - 1$" Rather than "Assume $P(k)$ is true." And then say that something along the lines of "We will show that when the inductive hypothesis holds $2^{k+1}<2^{k+2} + 2^{k} - 1$" – Doug M Jun 20 '17 at 16:42

1 Answers1

0

we have to prove that $$2^{k+1}\le 2^{k+2}-2^k-1$$ multiplying $$2^k\le 2^{k+1}-2^{k-1}-1$$ by $2$ we get $$2^{k+1}\le 2^{k+2}-2^k-2$$ and this is$$ \le 2^{k+2}-2^k-1$$

Dr. Sonnhard Graubner
  • 95,283