INDUCTION: Let a sequence of numbers $a_n$ for $n\in \mathbb N$ be defined by the following rule: $a_1 = 1$, and for $n>1$, $a_n = 2a_{n-1} + 1$

Question

Prove that $a_n = 2^n - 1$ for all $n\in\mathbb N$.

I don't see how the sub n and n to the power of anything can correlate. I'm missing something for I've been staring at the combinations I tried to work out for a couple hours now ._.

Please take a look at my edit!! – zoli Jul 19 '15 at 10:30 — zoli, Jul 19 '15 at 10:30
$$b_n=a_n+1\implies b_n=2b_{n-1}\ &\ b_1=2$$ – Did Jul 19 '15 at 10:48 — Did, Jul 19 '15 at 10:48

zoli · Accepted Answer · 2015-07-19T10:33:19.950

3

For $n=2$ the statement is true: $a_2=2a_1+1=3=2^2-1.$ Assume that the statement is true for all $2\le k \le n$. Then

$$a_{n+1}=2a_n+1=2( 2^n-1)+1=2^{n+1}-2+1=2^{n+1}-1.$$

We've proved the statement by mathematical induction.

edited Jul 19 '15 at 10:33

answered Jul 19 '15 at 10:04

zoli

20,452

INDUCTION: Let a sequence of numbers $a_n$ for $n\in \mathbb N$ be defined by the following rule: $a_1 = 1$, and for $n>1$, $a_n = 2a_{n-1} + 1$

1 Answers1