I would like most of the focus to be on the correctness of the answers but there is also obvsiously notation that needs to be corrected as well.

Prove each of the following:

1) $n \lt 2^n$ for n=1,2,3.... where $n \in \mathbb{N}$

Base case: n=1

LHS:1 RHS: 2

Therefore LHS $\lt$ RHS. Holds true for $n=1$.

Induction step:

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

$n + 1 \lt 2(n+1) \leq 2(2^n)$

notice that $n+1 \leq 2^n$ for $n \geq 1$

So we arrive at the conclusion that: $ n+1 \lt 2^{n+1}$ holds true for all $\mathbb{N}$

2) $2n+1 \lt 2^n$ for $n=3,4,5,6$ where $n \in \mathbb{N}$

Base case: $n=3$

LHS: 7 RHS: 8

Thus $LHS \lt RHS$ So this holds true for $n =3$

Inductive Step:

See if this holds true for $n \geq 3$

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

$2n+2 \lt 22^{n}$

$2(n+1) \lt 22^n$

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

Which holds true $\forall n \geq 3$


1 Answer 1


There are mistakes in both cases. In the proof of the first inequality you wrote $2(n+1)<2(2^{n})$ but you only know that $n <2^{n}$. Correct argument: $n+1 <2^{n}+1 < 2^{n}+2^{n}=2(2^{n})=2^{n+1}$.

In the second proof you wrote $2n+2$ for $2(n+1)+1$. This is wrong. Correct proof: $2(n+1)+1=2n+3=(2n+1) +2 <2^{n}+2 <2^{n}+2^{n}=2^{n+1}$.


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.