Explicit formula for recurrence relation

Question

I am given recurrence relation : a_n = 5a_n/2 + 3n, for n = 2,4,8,16... and a₂ = 1.
I found first 4 terms and I don't see a pattern.
a₄ = 5*1 + 3*4 = 17
a₈ = 5*17 + 3*8 = 109
a₁₆ = 5*109 + 3*16 = 593
a₃₂ = 5*1 + 3*4 = 3061
Playing a bit with it on a paper and calculater I found out formula that seems to be correct is : 5^n-1 - 3*2ⁿ + 2ⁿ⁺¹, but this was just a lucky guess.. And of course I won't be able to use a calculator on upcoming final exam.
Can anyone help me to solve such problems? Am I supposed to use iteration to find the general formula?

Answer 1

There are different types of recurrences . There are specific ways to attack each of them. Many book chapters are devoted for recurrence relations. It's a very interesting topic. You can start with this or Knuth.

The problem posted above, is a divide-&-conquer relation,

To solve such problems, we normally do a substitution followed by change of variable. Here,

we do this substitution, $ n = 2^k $ and $ b_k = a_{2^k}$. Then $$a_n = 5*a_{n/2} + 3*n$$ $$\implies a_{2^k}= 5*a_{2^{k-1}}+3*2^k$$ $$\implies b_k = 5*b_{k-1}+ 3*2^k$$

with $b_1 = a_2 =1$

Now we have converted the divide-&-conquer recurrence to a linear homogeneous recurrence of degree 1 and the main machinery that we use to solve this kind of recurrence relation is Generating functions and Characteristic Roots. But this is a very simple one and just after expanding two or three terms we can see the pattern. $$b_k = 5*b_{k-1}+ 3*2^k$$ $$\implies b_k = {5^2}*b_{k-2}+ 3*2^{k-1}*5+3*2^k$$ $$\implies b_k = {5^3}*b_{k-3}+ 3*2^{k-1}*5^2 +3*2^{k-1}*5+3*2^k$$ $$\implies b_k= 5^{k-1}*b_1 + 3 \sum_{j=0}^{k-2} 5^j 2^{k-j}$$ $$\implies b_k= 5^{k-1} + 3 \sum_{j=0}^{k-2} 5^j 2^{k-j}$$

And @angryavian has already shown in his/her answer that this is equal to $5^k−2^{k+1}$.

Answer 2

Let's look at the first few terms. $$a_2=1$$ $$a_4=5+3\cdot 4$$ $$a_8 = 5 a_4 + 3 \cdot 8 = 5(5+3 \cdot 4)+3 \cdot 8 = 5^2+3(5 \cdot 4 + 8)$$ $$a_{16}=5a_8+3 \cdot 16 = 5(5^2+3(5\cdot 4 + 8))+3 \cdot 16=5^3+3(5^2 \cdot 4 + 5 \cdot 8 + 16)$$

From here, you can see that the pattern is \begin{align*} a_{2^k} &= 5^{k-1} + 3 \sum_{j=0}^{k-2} 5^j 2^{k-j}\\ &= 5^{k-1} + 3 \cdot 2^k \cdot \frac{(5/2)^{k-1}-1}{(5/2)-1}\\ &= 5^{k-1} + 2^{k+1}((5/2)^{k-1}-1)\\ &= 5^{k-1}+5^{k-1} \cdot 4 - 2^{k+1}\\ &= 5^k-2^{k+1}. \end{align*}