# Proof verification induction on sequence

I am doing problems that involve inequalities. My understanding is that you through a string of inequalities show that one is less than the other. Kind of like the transitive property. For example:

$$2n+1 \lt 2^n$$ for $$n=3,4,...$$

Assume this is true for P(k):

Base case $$k = 3$$

$$LHS: 7 \space \space \space RHS: 8$$

$$LHS \space \space \lt \space \space RHS$$

This holds true for $$(k)$$

Prove for P(k+1):

$$2(n+1)+1 \lt 2^{n+1}$$

my understanding is that if I can find something that is greater than $$2(n+1)+1$$ and obviously below $$2^{n+1}$$ then the inequality holds true

$$2k+3 \lt 2^{k+1}$$

$$(2k + 1) + 2 \lt 2^k2$$

$$(2k+1) + 2 \lt 2^k + 2$$ by our hypothesis on $$k$$

It is very obvious that $$2^k + 2 \lt 2^k2$$ and doesn't need explanation so its safe to assume

$$2k+3 = (2k+1)+2 \lt 2^k + 2 \lt 2^k2$$

Thus $$(2k+3) \lt 2^k2$$

This seems perfectly logical to me since we are dealing with integers. These inequalities would not hold for $$\mathbb{R}$$.

I am having a hard time find a string of inequalities that proves $$n^2 \leq 2^n+1$$

Assume this holds true for $$k$$. $$P(k) = k^2 \leq 2^k+1$$ for $$n = 1,2...$$

Base case $$P(1):$$ $$LHS: 1 \space \space \space RHS: 3$$

$$LHS \space \space \leq \space \space RHS$$

holds true for $$P(k)$$

$$P(k+1)$$:

$$(k+1)^2 \leq 2^k + 1$$

$$k^2 + 2k + 1 \leq 2^k2+1$$

$$k^2 + 2k + 1 \leq 2^k +1 + 2k +1 \leq 2^k2+1$$

$$k^2 + 2k + 1 \leq 2^k + 2k + 2 \leq 22^k+1$$ by our hypothesis on $$k$$

I do not know where to go from here

• You say, "It is very obvious that $2^k+2<2\cdot2^k$ and doesn't need explanation..." but I highly recommend including even trivial steps into your work. Many teachers would see a line like this and would question if the student knew how to prove it (sometimes the obvious things are the hardest to prove). – Clayton Jul 29 '19 at 19:33
• Why did you bring up $\mathbb R$ when you said "This seems perfectly logical to me since we are dealing with integers. These inequalities would not hold for R"? Why bring up $\mathbb R$ at all? I also don't really understand what you mean by "string of inequalities". So I don't really understand what you are asking. – fleablood Jul 29 '19 at 22:10
• Why are you trying to show $n^2<2^n+1$? Was that the question? What was the question actually? Anyway; you've proven $2^n > 2n+1$; if if $k^2 < 2^k +1$ then $(k+1)^2 = k^2 + 2k + 1 < (2^k +1)+(2k+1) < (2^k+1) + 2^k= 2^{k+1} + 1$. – fleablood Jul 29 '19 at 22:49

## 3 Answers

You assume that $$k^2\leq 2^k+1$$ for some $$k\geq 1$$, and you want to prove that $$(k+1)^2\leq 2^{k+1}+1$$. Starting from the left-hand-side, you can proceed as follows:

\begin{align*} (k+1)^2 &= k^2+2k+1\\ &\leq (2^k+1) + 2k + 1, \end{align*} where the inequality follows from the induction hypothesis. If we can now show that

$$(2^k+1) + 2k + 1 \leq 2^{k+1},$$ then we we are done. By rearranging, this amounts to showing (for $$k\geq 1$$) that $$2k+2\leq 2^{k+1} - 2^k,$$ or

$$2(k+1)\leq 2^k(2-1),$$

or

$$2(k+1)\leq 2^k,$$

or

$$k+1\leq 2^{k-1}.$$

Oops! This last inequality is not true for all $$k\geq 1$$ like I hoped it would be. Don't worry about this, it happens. It doesn't mean that the original statement is wrong.

The last inequality fails for $$k=1$$ and $$k=2$$. But it does hold for all $$k\geq 3$$. I can remedy the proof by checking the base cases $$k=1$$, $$k=2$$, and $$k=3$$ in $$k^2\leq 2^k+1$$ by hand. Then I assume the induction hypothesis $$k^2\leq 2^k+1$$ for some $$k\geq 3$$, and I can proceed as above.

• UGH I cant believe I didnt think to subtract it over!! Thanks! – K. Gibson Jul 29 '19 at 21:58

In the first case, the proof is quasi-automatic. You want to prove

$$2n+1<2^n\implies 2n+3<2^{n+1},$$ or $$(2n+1)+2<2\cdot2^n.$$

Using the LHS,

$$(2n+1)+2<2^n+2$$ and we need to wonder when $$2^n+2\le2\cdot2^n.$$ This simplifies as $$2\le2^n$$ or $$n\ge1.$$

Done.

Now regarding the second case, we want to show

$$n^2<2^n\implies (n+1)^2<2^{n+1}$$ or $$n^2+2n+1<2\cdot 2^n.$$

By hypothesis

$$n^2+2n+1<2^n+2n+1$$ and we want

$$2^n+2n+1\le2\cdot 2^n$$ or $$2n+1\le2^n.$$

By a simple modification of the first proof, we can establish this result for $$n\ge2$$.

You can not use induction on $$\mathbb R$$ as the induction step will prove if it is true for $$x$$ then it is true for $$x+1$$ but there is nothing that will assure that it is true for any $$k; x < k < x+1$$.

Are you trying to prove $$2x + 1 < 2^x$$ for all real $$x\ge 1$$? If so do the following.

Use induction to prove that for $$n\in \mathbb N;n\ge 3$$ that $$2n+1 < 2^n$$.

Then prove that for any $$x \in \mathbb R$$; that if $$n < x < n+1$$ then $$2n+1 < 2x+1 < 2(n+1)+1$$ and $$2^n < 2^x < 2^{n+1}$$ so then only way that $$2^x \le 2x+1$$ could be possible is if $$2(n+1)> 2^n$$.

Why can prove that is impossible by induction by proving that $$2(n+1) \le 2^n; n\ge 3$$ and $$n\in \mathbb N$$.

So.....

Claim 1: $$2(n+1) \le 2^n$$ if $$n\in \mathbb N; n\ge 3$$.

Proof by Induction:

Base case: $$k=3$$ then $$2(3+1) = 2^3$$.

Induction case: If $$2(k+1) \le 2^k$$ then

$$2(k+2)= 2(k+1) + 2 \le 2^k+2 \le 2^k + 2^k = 2^{k+1}$$.

Thus we have proven so for all natural $$n> 3$$ that $$2(n+1)\le 2^n$$

So as $$2a+1 < 2(n+1)=2n + 2\le 2^n$$ we have proven $$2n+1 < 2^n$$ for all natural $$n \ge 3$$.

Now if $$x\in \mathbb R; x \ge 3$$ then there is an $$n$$ so that $$n < x < n+1$$ then $$2n+1 < 2x + 1 < 2n+2 \le 2^n$$. And $$2^x = 2^n*2^{x-n}$$. As $$x-n >0$$ we know $$2^{x-n} > 1$$ so $$2^n < 2^n*2^{x-n} = 2^x$$. And so $$2x+1 < 2^x$$. And that's that.

Then you sweitch gears and ask how to prove $$n^2 \le 2^n + 1;n \ge 3$$. (Was that part of the question? A different question?

Well, base case is easy: $$3^2 = 2^3 + 1$$.

Induction follows:

If $$k^2 \le 2^k + 1$$ then

$$(k+1)^2 = k^2 + 2k + 1 \le 2^k + 2k + 1 = 2^k + 2(k+1)$$. Above we proved that $$2(n+1) \le 2^k$$ if $$k \ge 3$$ so $$2^k + 2(k+1) \le 2^k + 2^k = 2^{k+1}$$.

• I have a question with regards to proof one. Do I really have to go beyond $2^n + 2 \lt 2^n2$? That is already enough to use the transitive property to show that $2(n+1)+1 \lt 2^(n+1)$ – K. Gibson Jul 29 '19 at 23:42
• I'm probably not going to see connections like that on a test. This is introductory material for Real Analysis. – K. Gibson Jul 29 '19 at 23:44
• You need to actually state your results. – fleablood Jul 30 '19 at 0:05