General form for the recurrence relation $a_{n+1} - a_n = 4^n$

Question

So... I just learned about discrete, and I'm trying to solve this problem, finding the general term I guess : $$ a_1 = 1,\qquad a_{n+1} - a_n = 4^n\, \text{ for all } n\geq 1 $$

I looked at some examples and found that the solution is $a_n = \frac{1}{3}(4^n - 1)$. Can anyone explain this?

Answer 1

Start with what you know: for every $n\geq 1$, $$ a_{n+1}-a_n = 4^n \tag{1} $$ Now, what happens if you sum this equation (1), for $n$ ranging from $1$ to some $N\geq 1$? $$ \sum_{n=1}^N (a_{n+1}-a_n) = \sum_{n=1}^N 4^n \tag{2} $$ But the left-hand-side is a telescopic series: $$ \sum_{n=1}^N (a_{n+1}-a_n) = (a_{N+1} - a_N) + (a_N-a_{N-1})+\dots + (a_2-a_1) = a_{N+1} - a_1 $$ but the right-hand-side is a geometric sum, equal to $$ 4\cdot\frac{4^N-1}{4-1} = \frac{4}{3}(4^N - 1) $$

Therefore, you end up with $ a_{N+1} - 1 = \frac{4}{3}(4^N - 1) $ or equivalently $$ a_{N+1} = \frac{1}{3}(4^{N+1} - 1) $$ for $N\geq 1$.

Answer 2

Let a_n=c(lamda)^n be a solution to a_n+1 - a_n = 4^n so we have c(lamda)^n)(lamda-1)=4^n which is c(lamda-1)=(4/lamda)^n so if lamda is 4 RHS is 1 so c(4-1)=1 so c=1/3 therefore a_n=1/3 (4)^n solves a_n+1 - a_n = 4^n yet a_1=1 so then a_1= 1/3 (4) needs to be adjusted by 1/3 so we have a_n=1/3 (4^n-1)