Question

Find the general term of {a_n}

Answer 1

From the given recurrence, it follows that

$a_{n+1} = 2a_n + 1 \\\\ a_{n+1} = 2(2a_{n-1} + 1) = 2^2a_{n-1} + 1 + 2 \\\\ a_{n+1} = 2^2(2a_{n-2}+1) + 1 + 2 = 2^3a_{n-2} + 1 + 2 + 2^2 \\\\ a_{n+1} = 2^3(2a_{n-3} + 1) + 1 + 2 + 2^2 = 2^4a_{n-3} + 1 + 2 + 2^2 + 2^3$

and so on down to the first term,

$a_{n+1} = 2^na_1 + \displaystyle \sum_{k=0}^{n-1}2^k$

(Notice how the exponent on the 2 and the subscript of a in the first term add up to n + 1.)

Denote the remaining sum by S ; then

$S = 1 + 2 + 2^2 + \cdots + 2^{n-1}$

Multiply both sides by 2 :

$2S = 2 + 2^2 + 2^3 + \cdots + 2^n$

Subtract 2S from S to get

$S - 2S = 1 - 2^n \implies S = 2^n - 1$

So, we end up with

$a_{n+1} = 4\cdot2^n + S \\\\ a_{n+1} = 2^2\cdot2^n + 2^n-1 \\\\ a_{n+1} = 2^{n+2} + 2^n - 1 \\\\\implies \boxed{a_n = 2^{n+1} + 2^{n-1} - 1}$