0

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

$ f(0) = 1 $

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

Adalynn
  • 335

1 Answers1

3

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.

BigbearZzz
  • 15,084
  • It might be helpful to the author to note that for even $n$ one has $2^{n}k!=n!!$ where $n!!$ is the double factorial $n(n-2)(n-4)\ldots$ and that $2^{n-1}(n-1)!/(k-1)!=(n-1)!!$, so even $n$ has $f(n)=\frac{n!!}{(n-1)!!}$. (Or to give some other explanation of how these identities are arrived at) – Milo Brandt Jun 19 '16 at 16:15
  • Ok, I'll edit accordingly. – BigbearZzz Jun 19 '16 at 16:16