0

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.

Michael Hardy
  • 1
John
  • 139
  • the issue with this recurrence isn't that it has no coefficients, but that it's non-linear. The coefficient of $a_{2n-2}$ is $(2n-1)$ –  Oct 21 '14 at 17:10
  • also, this sequence is only defined for even $n$ at the moment –  Oct 21 '14 at 17:11
  • Hint: see what $a_{2n-2}, a_{2n-4}, \cdots$ would be. – Prajwal Kansakar Oct 21 '14 at 17:13
  • @krey: It is linear. But the coefficients are not constant. – Hans Lundmark Oct 21 '14 at 19:15
  • @HansLundmark, I wouldn't say that the differential equation $y(2x)=(2x-1)y'(2x)$ is linear. I'm using the same definition of linear –  Oct 21 '14 at 20:35
  • That's definitely a linear ODE! If $y_1$ and $y_2$ are solutions, then so is $c_1 y_1 + c_2 y_2$ for any constants $c_1$ and $c_2$. But it has non-constant coefficients. – Hans Lundmark Oct 22 '14 at 06:49

2 Answers2

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!}$$

  • it seems to me that we just take $a_{n-2}$ and muliply with (2+$a_{n-2}$) to get the answer for the next sequence, so $a_{2n} = a_{n-2} * (2+a_{n-2}) $ or maybe my brain is not working.. – John Oct 21 '14 at 17:30
  • The second clause of your disjunction holds. You just traded the initial recurrence for another that is wrong, and didn't get any closer to the solution :( –  Oct 21 '14 at 17:34
  • i see the pattern and understand why double factorial works, gotta look a bit more into it I suppose. Thanks anyway – John Oct 21 '14 at 17:40
0

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!}\;.$$

Brian M. Scott
  • 616,228