Problems with Recurrence Relations as a form of Counting

Question

I have been having trouble trying to understand how to do the following problem

Solve by unfolding: $a_0=3$, and for $n\geq1$, $a_n=5a_{n-1}+3$. Hint: This will involve the geometric sum formula.

---

This is my work so far: $$a_n=5a_{n-1}+3$$ $$a_n=5(5a_{n-2}+3)+3$$ $$a_n=(5(5(5a_{n-3}+3)+3)+3)$$ $$a_n=5^{n}*a_0+5^{n-1}*3+5^{n-2}*3+...+5*3+3$$ I am not sure if this is right, or how to really do this problem. Help, and hints would be much appreciated.

Answer 1

EDIT : just noticed that the problem says solve by unfolding which is not really smart in my opinion, but I'll leave this answer as this is the way to go with these sequences (arithmetico-geometric).

This is a classic of arithmetico-geometric sequence. There's a classic formula but there's no need to learn it, you can demonstrate it every time you need it. $$\text{Let's use }l = \frac{3}{1-5} = -\frac{3}{4}$$ This number is not random, it comes from solving the fixed point of the sequence : $$ l = 5 \times l + 3$$. Now let's notice this : $$\begin{align} \begin{split} a_{n+1} - l &= 5a_{n} + 3 - l \\ &=5(a_{n}+\frac{3}{5}+\frac{3}{20}) \\ &=5(a_{n}+\frac{15}{20}) \\ &=5(a_{n}-\frac{-3}{4}) \\ &=5(a_{n}-l) \end{split} \end{align}$$ We notice that the sequence $b_{n} = a_{n} - l$ is geometric. You can then use your geometric formula to get that : $b_n = 5^n\times b_0$ with $b_0 = 3 -l = \frac{15}{4}$.

Then, problem is solved : $$\begin{align}\begin{split}a_n &= b_n + l\\ &=5^n \times \frac{15}{4} - \frac{3}{4}\\ &= \frac{3}{4}(5^{n+1}-1) \end{split}\end{align}$$ For further investigation, solve it using the general formula : $u_{n+1} = au_{n} + b$ with the same methodology to find out that : $u_n = a^n(u_0 -l) + l \text{ with } l = \frac{b}{1-a}$

Answer 2

Hint

Considering $$a_n=5a_{n-1}+3$$ let $a_n=b_n+c$ and replace to get $$b_n=5 b_{n-1}+4 c+3$$ Now, select the "good" $c$.

Answer 3

Your method works great, but you can continue and simplify the result (using the formula for geometric sum): $$ \alpha_n = 5^n \cdot \alpha_0 + 5^{n-1} \cdot 3 + 5^{n-2} \cdot 3 + ... + 5 \cdot 3 + 3 = \\ 5^n\cdot \alpha_0 + 3\sum_{k=0}^{n-1}5^k = 5^n \cdot \alpha_0 + 3 (\frac{5^n-1}{5-1})=5^n \cdot \alpha_0 +3\frac{5^n-1}{4} $$

Answer 4

\begin{align} a_n &= 5a_{n-1}+3\\ &= 5(5a_{n-2}+3)+3\\ &= 5^2a_{n-2}+3(5^1+5^0)\\ &= 5^2(5a_{n-3}+3)+3(5^1+5^0)\\ &= 5^3a_{n-3}+3(5^2+5^1+5^0)\\ &= \dots\\ &= 5^na_0+3(5^{n-1}+\dots+5^0)\\ &= 5^n(3)+3\cdot\frac{5^n-1}{5-1}\\ &= 3\cdot5^n+\frac34(5^n-1)\\ &= \frac{15}4\cdot5^n-\frac34\\ &= \frac34(5^{n+1}-1) \end{align}