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$
  • 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 '19 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 '19 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 '19 at 22:49
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$
  • $\begingroup$ UGH I cant believe I didnt think to subtract it over!! Thanks! $\endgroup$ – K. Gibson Jul 29 '19 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$
  • $\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 '19 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 '19 at 23:44
  • $\begingroup$ You need to actually state your results. $\endgroup$ – fleablood Jul 30 '19 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.