# Solving a recurrence using substitutions

I have to solve this recurrence using substitutions:

$(n+1)(n-2)a_n=n(n^2-n-1)a_{n-1}-(n-1)^3a_{n-2}$ with $a_2=a_3=1$.

The only useful substitution that I see is $b_n=(n+1)a_n$, but I don't know how to go on, could you help me please?

-

it seems that I solved. $$(n-2)b_n=(n^2-n-1)b_{n-1}-(n-1)^2b_{n-2}$$

So divide it by $n-1$ then we get \begin{align*} \left(1-\frac{1}{n-1}\right)b_n&=\left(n-\frac{1}{n-1}\right)b_{n-1}-(n-1)b_{n-2}\\ &=\left(n-1+1-\frac{1}{n-1}\right)b_{n-1}-(n-1)b_{n-2}\\ &=(n-1)(b_{n-1}-b_{n-2})+b_{n-1}\left(1-\frac{1}{n-1}\right) \end{align*}

then $$\left(1-\frac{1}{n-1}\right)(b_n-b_{n-1})=(n-1)(b_{n-1}-b_{n-2})$$

then we make subtitution $p_n=b_n-b_{n-1}$ as $b_2=3,b_3=4$ we get that $p_3=1$.

we have that \begin{align*} &\left(1-\frac{1}{n-1}\right)p_n =(n-1)p_{n-1} \implies\\ &p_n=\frac{(n-1)^2}{n-2}p_{n-1}\implies\\ &p_n=\prod\limits_{k=4}^n{\frac{(k-1)^2}{k-2}}=\frac{n-1}{2}\frac{(n-1)!}{2} \implies\\ &b_n-b_{n-1}=\frac{n!-(n-1)!}{4} \implies\\ &b_n=4+\sum\limits_{k=4}^n{\frac{k!-(k-1)!}{4}}=4+\frac{1}{4}(n!-6)=\frac{10+n!}{4} \implies\\ &a_n=\frac{10+n!}{4(n+1)} \end{align*}

-
Bravo!${}{}{}{}$ – Gerry Myerson Oct 19 '11 at 3:28
This is a bit hard to read -- you may want to consider using displayed equations and align/eqnarray environments. You get displayed equations by enclosing them in double dollar signs, and if you don't know how to use align/eqnarray, you can right-click on any aligned formulas you see (e.g. here) and select "Show Source" to see how it's done. – joriki Oct 19 '11 at 6:28
Sorry, I'll try use it. – Evgeny Savinov Oct 19 '11 at 6:51

So if $b_n=(n+1)a_n$, then $b_{n-1}=na_{n-1}$, and $b_{n-2}=(n-1)a_{n-2}$, and you equation becomes $$(n-2)b_n=(n^2-n-1)b_{n-1}-(n-1)^2b_{n-2}$$ which is a little simpler than what you started with, though I must admit I can't see offhand any easy way to get to a solution from there. Are you working from a text or some notes that have other examples of solving via substitution? Maybe there's a hint in some other example as to how best to proceed.

-
Now if $c_n=nb_n$ you have $c_n-2b_n=n^2b_{n-1}-c_{n-1}-c_{n-2}-(n^2-n-3)b_{n-2}$. I don't know if that helps. – Ross Millikan Oct 19 '11 at 3:19