# Problems with Recurrence Relations as a form of Counting

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.

• I think you have some typos because, for example, $\alpha_2$ does not equal that. i guess you meant to write $\alpha_n$ on the left and $\alpha_{n-2}$ on the right Jul 18 '18 at 9:14
• I don't really know how to go forward with the question. I don't even understand much of my own work there. Happy nd willing to award an answer if one is given, though! @MrFatzo
– user568999
Jul 18 '18 at 9:16

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$.

• Where did you get the $4c$ from, though?
– user568999
Jul 18 '18 at 9:23
• $b_n+c=5b_{n-1}+5c+3$ Jul 18 '18 at 9:24
• But why does the $c$ $\neq$ $3$? In what step do we assign a value to $c$?
– user568999
Jul 18 '18 at 9:26
• @MichaelByrne. What happens if $4c+3=0$ ? Does it start looking familiar to you ? Jul 18 '18 at 9:34

\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}

• Is that the answer? What's the ... for?
– user568999
Jul 18 '18 at 9:27
• where did $a_0$ go? Jul 18 '18 at 9:27
• Oh, I have no clue. This is the question posed. Verbatim from our text.
– user568999
Jul 18 '18 at 9:28
• @MrFatzo $a_0=3$ Jul 18 '18 at 9:28
• I don't see use of the geometric sum formula, and I wish there was some work shown for the "..." step. I would b more inclined to award an answer given these two conditions.
– user568999
Jul 18 '18 at 9:50

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}$$

• For your final bit there, is it $3$ $\frac{5^{n}-1}{4}$ or $3$ $\frac{5^{n+1}-1}{4}$ as suggested above by Karn Watcharasupat?
– user568999
Jul 18 '18 at 9:47
• It's $5^n$ in my answer. The exponent is the number of terms in the sum and we are going from 0 to $n-1$, which are n terms Jul 18 '18 at 9:49
• So you and Karn are both correct? I appreciate your answer quite a bit. +1 there...but there are two different answers I must consider now.
– user568999
Jul 18 '18 at 9:51

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}$