Does the explicit formula for recurrence relation exist

76 Views Asked by At

Does an explicit formula exist for this recurrence relation? If so, what is it?

$ f(0) = 1 $

$ f(n) = \frac{n}{f(n-1)} $

1

There are 1 best solutions below

2
On BEST ANSWER

If $n>0$ is even, then $$ f(n)=\frac{2^{n-1}\cdot k!\cdot(k-1)!}{(n-1)!} $$ for $n=2k.$ For odd $n$, we have $$ f(n)=\frac{n!}{2^{n-1}\cdot (k!)^2 } $$ for $n=2k+1$.

Edit: To obtain the result, one observes that $$ f(n)=\frac{n(n-2)(n-4)\ \dots}{(n-1)(n-3)\ \dots}\ , $$ the dots end in $1$ or $2$ depending on weather $n$ is odd or even. Then we merely collect the terms to arrive at the formula I described.

Note that we can express $f$ using the Double Factorial notation, as mentioned in Mr. Milo's comment.