# Tricks to Solve Arbitrary Recursions

Consider two recursions:

(1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$

(2) $na_n = (n-2)a_{n-1} + n/2$ with $a_0 = 0$

When I look at the first recursion it suggests to me that I should use a characteristic equation and then solve the non-homogeneous component by undetermined coefficients. However, I know that because of the way $\phi(n) = 4n3^n$, the non-homogeneous component, is set up it will be difficult (it seems to me) to find a good guess.

When I look at the second I think that there must be some way to rearrange the n's so that I can set up a recursion $b_n$ as a substitute for $a_n$.

Are there better ways to think about how to deal with these recursions? How can I be more efficient and avoid excessive time in calculations (e.g. as I would imagine the characteristic method for (1) would require)? Any help is very much appreciated.

• See here for a related problem. – Mhenni Benghorbal Apr 19 '13 at 13:17
• That does seem useful for the first of the two recurrences, though it does use the characteristic method, long calculations and substitutions included. I will look at it in more detail. – user73041 Apr 19 '13 at 13:21

## 2 Answers

For the second one there exists a formula

$$a_n = \left(\prod_{k=0}^{n-1} f_k \right) \left(a_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}\right),$$

which is a solution of the first order recurrence relation

$$a_{n+1} - f_n a_n = g_n \longrightarrow (1).$$

In your case, you can write the recurrence as (by shifting the index $n \leftrightarrow n+1$)

$$(n+1)a_{n+1} = (n-1)a_{n} + (n+1)/2 \implies a_{n+1} - \frac{(n-1)}{n+1}a_{n} = 1/2\quad a_0=0.$$

Now, you can compare your recurrence with eq $(1)$ and just use the formula. Here is your final answer

$$a_1 = \frac{1}{2},\quad a_n=\frac{n+1}{6},\quad n\geq 2.$$

• I appreciate your response, but that solution is a bit above my level and I am not sure what it means. Is there an explanation for it? – user73041 Apr 19 '13 at 13:39

First change $a_n=3^nb_n$: $$9b_{n+2}=6b_{n+1}-b_n+4n$$

Do you end the solution?

• Yes, in this case the particular solution could just be of the form (An + B) and the homogeneous solution is solved in the usual way. Very nice substitution. – user73041 Apr 19 '13 at 14:25