Induction on inequalities

51 Views Asked by At

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

There are 1 best solutions below

0
On BEST ANSWER

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