Recurrence question

Question

My question relates to the following recurrence relation:

$$a_{j+2}=\frac{a_{j}}{2}$$

The book which I am reading says that the (approximate) solution is given by:

$$a_{j}=\frac{C}{(j/2)!}$$

(I think there was an assumption of large $j$, too)

Could anyone give me a hand to understand how to arrive at this solution or give me guidelines on how to deal with recurrence relations and convert them to factorials?

Answer 1

This is not (quite) correct. You will have $\frac j2$ steps down to zero, so the solution will be $a_j=\frac {a_0}{2^{\frac j2}}$ as each step divides by $2$. To get a factorial, you would need to see $j$ in the recurrence relation, say $a_{j+2}=\frac {a_j}{j/2}$

Answer 2

I'm at a loss why one would consider a solution involving a factorial. Rather it is easily seen that:

$$a_j = \begin{cases}2^{-j/2}a_0 & \text{if $j$ is even} \\ 2^{-(j-1)/2}a_1 & \text{if $j$ is odd}\end{cases}$$

e.g. by mathematical induction.

Answer 3

This is a second-order recurrence with general solution

$$a_n = A (-1)^n 2^{-n/2} + B 2^{-n/2}$$

You can see this from the equation

$$2 a_{n+2} - a_n = 0$$

which has a characteristic equation

$$2 r^2-1=0 \implies r=\pm \frac{1}{\sqrt{2}}$$