Discrete Math Recursion Question

Question

I'm stuck and I was wondering if anyone could point me in the right direction

Oh, Im so sorry! I forgot to state what I'm to do with it. It asks me to find a explicit formula for the recursion

$$\begin{align*} a_1&= 3\\ a_n&= 5a_{n-1} + 12 \end{align*}$$

So i found

$$\begin{align*} a_1&=3\\ a_2&=27\\ a_3&= 147\\ a_4&= 747 \end{align*}$$

So far I'm stuck. I can try writing the summation in a different way but I just cannot figure it out

Answer 1

Since it’s a first-order recurrence, you can try the very elementary technique of ‘unwinding’ it:

$$\begin{align*} a_n&=5a_{n-1}+12\\ &=5(5a_{n-2}+12)+12\\ &=5^2a_{n-2}+5\cdot12+12\\ &=5^2(5a_{n-3}+12)+5\cdot12+12\\ &=5^3a_{n-3}+5^2\cdot12+5\cdot12+12\\ &\;\vdots\\ &=5^ka_{n-k}+12(5^{k-1}+5^{k-2}+\ldots+5+1)\tag{1}\\ &\;\vdots\\ &=5^{n-1}a_{n-(n-1)}+12\sum_{k=0}^{n-2}5^k\\ &=5^{n-1}a_1+12\sum_{k=0}^{n-2}5^k\\ &=3\cdot5^{n-1}+12\sum_{k=0}^{n-2}5^k\;. \end{align*}$$

You should know how to express that last summation in closed form, and when you’ve done that, you’ll have a closed form for $a_n$. Of course we guessed at a pattern in line $(1)$, so the closed form that you get should be considered a conjecture, but once you have it, it’s easy enough to prove by induction that it’s correct.

This answer illustrates another, somewhat neater technique for solving exactly this kind of recurrence.

Answer 2

try for characteristic equation : $$a_n=5a_{n-1}+12\\r=5\\a_n=c_1r^n+c_2\\a_n=c_1(5)^n+c_2\\$$apply now $a_1=3,a_2=27$ to find $c_1,c_2$ $$a_1=3=c_15+c_2\\a_2=27=c_125+c_2\\a_n=\frac{6}{5}(5)^n-3\\a_n=6(5)^{n-1}-3$$

Answer 3

If substitute $a_{n-2}$, $a_{n-3}$, and so on, we have: $$a_n=5^k \cdot a_{n-k} + 12 \cdot \sum_{i=0}^{k-1}5^i$$ $$a_n=5^k \cdot a_{n-k} + 12 \cdot {{5^k-1} \over {5-1}}$$ $$a_n=5^k \cdot a_{n-k} + 3 \cdot {(5^k-1)}$$ Let: $k=n-1$, then $n-k=1$ $$a_n=5^{n-1} \cdot a_{1} + 3 \cdot (5^{n-1}-1)$$