2
$\begingroup$

This question already has an answer here:

I'm trying to do homework problems and for the most part I've been getting the results. For this one though, I am having some trouble since its $2^n$ and I can't relate it properly:

Prove using simple induction that $n < 2^n$ for all $n \ge 1$.

So obviously, the basis step holds as $1 < 3$. Now, I assume that $n = k$ holds as well and have to prove for $n=k+1$. This is the step I am having trouble with as I cannot relate the induction hypothesis with what I want to end up with. Can anybody show me a model solution for this one? I think my trouble comes because of the $2^n $

$\endgroup$

marked as duplicate by GNUSupporter 8964民主女神 地下教會, Mohammad Riazi-Kermani, StubbornAtom, Robert Soupe, B. Mehta May 10 '18 at 18:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

For the inductive step:

$$n+1\le 2n<2\times 2^n=2^{n+1}$$

$\endgroup$
3
$\begingroup$

a hint: you need to show that $$ n + 1 < 2^{n+1}$$ observe that $$ 2^{n+1} = 2 \cdot 2^{n} = 2^n + 2^n$$ now use your induction hypothesis to estimate $2^n$. also observe that $1$ is the smallest natural number, i.e. $1 \leq n$

$\endgroup$
0
$\begingroup$

Hints:

  1. For all $n\ge 1$, $2^n>n>1$
  2. $2^{n+1}=2\cdot 2^n=2^n+2^n>2^n+1$
$\endgroup$
0
$\begingroup$

Yo know that $k<2^k$ and you want to prove $k+1<2^{k+1}$, but it's equal:

$$k+1<2^{k+1}=2^k+2^k$$

By induction hipothesis you know that $k<2^k$ and on the other hand it's clear that $1 \leq 2^{k}$. If you add this inqeualities side by side you get $k+1<2^k+2^k=2^{k+1}$.

$\endgroup$

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