What's the procedure for solving recurrence relations without coefficients?

Question

I've a recurrence relation

$$a_{2n}=(2n-1) a_{2n-2}$$

(intial condition $a_2 = 1$)

which has no coefficients, so I can't follow the standard procedure where I find the roots from which we can set up the general solution and then proceed to find alpha etc.

Is there any procedure, that I don't know of, that you follow when you encounter such a recurrence relation with no coefficients? No examples of this kind is in my book and I've looked on the web as well for answers but none found.

Answer 1

$$a_2=1$$ $$a_4=3.1$$ $$a_6=5.3.1$$ $$a_8=7.5.3.1$$ $$...$$ Evaluate the first terms and find a pattern. $$a_{2n}=(2n-1)!!=\frac{(2n)!}{2^nn!}$$

Answer 2

Since each term depends only the previous term, you can ‘unwind’ it:

$$\begin{align*} a_{2n}&=(2n-1)a_{2n-2}\\ &=(2n-1)(2n-3)a_{2n-4}\\ &\;\vdots\\ &=(2n-1)(2n-3)\ldots\big(2n-(2k-1)\big)a_{2n-2k}&\text{after }k\text{ steps}\\ &\;\vdots\\ &=(2n-1)(2n-3)\ldots(3)a_2&\text{after }n-1\text{ steps}\\ &=\prod_{k=1}^n(2k-1)\\ &=(2n-1)!! \end{align*}$$

Properly speaking you should then prove by induction that the formula $a_{2n}=(2n-1)!!$ is correct, since the ‘unwinding’ technique is really just a more sophisticated form of pattern spotting: when I write the expression showing the result of $k$ steps, I’m extrapolating the pattern that I see in the first few steps.

If you want to get rid of the double factorial, note that

$$(2n-1)!!=\frac{(2n)!}{(2n)(2n-2)\ldots(2)}=\frac{(2n)!}{2^nn!}\;.$$