Explicit formula for recurrence relation I am given recurrence relation : an = 5an/2 + 3n, for n = 2,4,8,16... and a2 = 1. 
I found first 4 terms and I don't see a pattern.
a4 = 5*1 + 3*4 = 17
a8 = 5*17 + 3*8 = 109
a16 = 5*109 + 3*16 = 593
a32 = 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 : 5n-1 - 3*2n + 2n+1, 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?
 A: 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*}
A: 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}$.
