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