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 ._.

Answer 1

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.