2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ See here for a related problem. $\endgroup$ – Mhenni Benghorbal Apr 19 '13 at 13:17
  • $\begingroup$ 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. $\endgroup$ – user73041 Apr 19 '13 at 13:21
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – user73041 Apr 19 '13 at 13:39
1
$\begingroup$

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

Do you end the solution?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – user73041 Apr 19 '13 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.