TITLE: Find the solution to recurrence relation and initial conditions. Use an iterative approach.
QUESTION [0 upvotes]: $$A(n)=3A(n-1)+1, A(0)=1$$
the solution from the textbook is $$A(n)=\dfrac{3^{n+1}-1}2$$
But I am having trouble to understand how we get this answer.

REPLY [0 votes]: Start with
$$
A(n)=3A(n-1)+1\quad\text{and}\quad A(0)=1
$$
Multiply by $3^{-n}$
$$
3^{-n}A(n)=3^{1-n}A(n-1)+3^{-n}
$$
Substitute $B(n)=3^{-n}A(n)$
$$
B(n)=B(n-1)+3^{-n}\quad\text{and}\quad B(0)=1
$$
Apply the sum of a geometric series
$$
B(n)=\frac{1-3^{-n-1}}{1-3^{-1}}
$$
Back substitute to get
$$
A(n)=\frac{3^{n+1}-1}2
$$
{"set_name": "stack_exchange", "score": 0, "question_id": 3482367}