Using induction to prove $a_n >2^n$

Question

For the sequence $a_n=2a_{n-1}+1$ where $a_0=1$

Show that $a_n>2^n$ using induction.

Use proof by contradiction (minimum counterexample).

Attempt: 1. I assume, that $a_n>2^n$ as my induction hypothesys. Now, I try to show that $$a_{n+1}>2^{n+1} \\ 2a_{n}+1>2^{n}*2 \\ a_n+1/2>2^n$$ and I am stuck and dont know how to proceed.

2$.$ Let set $S=(n\in Z_+: a_n\le 2^n)$ be a set of counterexamples. Let $m$ be the smallest element of $S$, then $m-1 \notin S$. Then, I try to produce a contradiction $$a_{m-1}\le2^{m-1} \\ a_{m}\le 2^m+1$$ and again I am stuck. Help apreciated. Thanks.

score 2 · Accepted Answer · answered Nov 18 '13 at 17:06

2

You know that $a_1 = 3 > 2^1$, so assume that $a_n > 2^n$. Then, $$ a_{n+1} = 2a_n + 1 > 2\cdot 2^n + 1 = 2^{n+1} + 1 > 2^{n+1} $$ So, by induction, $a_n > 2^n$ for all $n\in \mathbb{N}$

answered Nov 18 '13 at 17:06

Prahlad Vaidyanathan

31,554

Awesome. Now, I will try to figure out the second part. – Koba Nov 18 '13 at 17:09
1

Yes, Let $m$ be the smallest number such that $a_m \leq 2^m$. Then check that $a_{m-1} \leq 2^{m-1}$ as well. – Prahlad Vaidyanathan Nov 18 '13 at 17:11

score 1 · Answer 2 · answered Nov 18 '13 at 17:09

1

$a_n > 2^n\Rightarrow 2a_n > 2^{n+1}\Rightarrow 2a_n+1> 2^{n+1}+1\Rightarrow a_{n+1}>2^{n+1}+1> 2^{n+1} \text{ i.e.,} a_{n+1}>2^{n+1}$

answered Nov 18 '13 at 17:09

Using induction to prove $a_n >2^n$

2 Answers2