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

$ f(0) = 1 $

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


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.

  • $\begingroup$ 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) $\endgroup$ – Milo Brandt Jun 19 '16 at 16:15
  • $\begingroup$ Ok, I'll edit accordingly. $\endgroup$ – BigbearZzz Jun 19 '16 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.