1
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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). $\endgroup$
    – Clayton
    Jul 29, 2019 at 19:33
  • $\begingroup$ 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. $\endgroup$
    – fleablood
    Jul 29, 2019 at 22:10
  • $\begingroup$ 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 $. $\endgroup$
    – fleablood
    Jul 29, 2019 at 22:49

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ UGH I cant believe I didnt think to subtract it over!! Thanks! $\endgroup$
    – K. Gibson
    Jul 29, 2019 at 21:58
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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)$ $\endgroup$
    – K. Gibson
    Jul 29, 2019 at 23:42
  • $\begingroup$ I'm probably not going to see connections like that on a test. This is introductory material for Real Analysis. $\endgroup$
    – K. Gibson
    Jul 29, 2019 at 23:44
  • $\begingroup$ You need to actually state your results. $\endgroup$
    – fleablood
    Jul 30, 2019 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.