How would I go about converting $U(n)= 4^n+U(n-1)$ into an explicit form?

Question

I have the recursive function $U(n)= 4^n+U(n-1)$, and I'd like to convert it into an explicit form. If you could also walk me through the process that would be great. Thanks!

Answer 1

Rearrange a bit to get

$$u_n - u_{n-1} = 4^n$$

Then do a summation on both sides:

$$\sum_{k = 1}^n(u_k - u_{k-1}) = \sum_{k = 1}^n4^k$$

Observe the cancellations on the LHS, and deduce that

$$u_n - u_0 = \sum_{k = 1}^n4^k$$

Now, the RHS is just the sum of an everyday geometric progression. To find this sum, let $S = \sum_{k = 1}^n4^k = 4^1 + 4^2 + \dots + 4^n$. Then,

$$4S - S = (4^2 + 4^3 + \dots + 4^n + 4^{n+1}) - (4^1 + 4^2 + \dots + 4^n)$$ $$3S = 4^{n+1} - 4$$ $$S = \frac{4^{n+1} - 4}{3}$$

So,

$$u_n - u_0 = \frac{4^{n+1} - 4}{3}$$ $$u_n = u_0 + \frac{4^{n+1} - 4}{3}$$