Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please help in finding the solution of this recursion.

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

where $ f(1)=1$ and $f(2)=2$.

share|cite|improve this question
I tried that already..But it blocks the way of further thinking – Rejo_Slash Jul 29 '14 at 2:38
I tried to visualize a tree and get the count. I also tried to find common pattern . I couldnt convert it to a solvable recursion format – Rejo_Slash Jul 29 '14 at 2:53
With $a_n = \log f(n)$ the recursion relation becomes $a_n - a_{n-1} - a_{n-2} = -\log n$. However, finding the particular solution seems tricky though... – Winther Jul 29 '14 at 2:56
up vote 4 down vote accepted

Take some large n, $$ \begin{align} f(n) &= \frac{f(n-1) f(n-2)}{n} \\ &= {f(n-2)^2 f(n-3) \over n (n-1)} \\ &= {f(n-3)^3 f(n-4)^2 \over n (n-1) (n-2)^2} \\ &= \frac{f(n-4)^5 f(n-5)^3}{n (n-1) (n-2)^2 (n-3)^3} \\ &= \dots \\ &=\frac{f\left(n - (n-2) \right)^{F_{n-1}} f\left(n - (n-1) \right)^{F_{n-2}}}{\prod^{n-3}_{i=0} (n-i)^{F_{i+1}}} \\ &=\frac{2^{F_{n-1}}}{\prod^{n-3}_{i=0} (n-i)^{F_{i+1}}} \end{align} $$ in each step until the "..." I just plugged the formula into the left factor of the numerator until I saw a pattern. The symbol $F_n$ denotes the Fibonacci sequence, which follows $F_n = F_{n-1} + F_{n-2}$ and $F(0) = 0$ and $F(1) = 1$. Sorry this is not a formal proof, but you can easily prove it by induction by showing that, if it's true for some large n then it must be true for n+1, and then simply demonstrating that it's true for 3.

share|cite|improve this answer

I believe the formula is, for $n\geq 3$,

$$f(n) = 2^{F_{n-1}}\prod_{k=3}^{n}k^{-F_{n-k+1}}$$

where $F_1,F_2,F_3,\ldots$ is the standard Fibonacci sequence whose first two terms are $1$.

You can see this by just writing out the first several terms. For example,

$$f(9) =\dfrac{2^{21}}{3^{13}4^8 5^5 6^3 7^2 8^1 9^1} $$

Addendum (Inductive Proof): The base case ($n=3$) is trivial, since $$f(3)=\dfrac{f(2)f(1)}3=\dfrac{2\cdot 1}3 = \frac23=2^1 3^{-1}=2^{F_2}3^{-F_1}$$

For the inductive step, suppose the formula holds for $3,\ldots,n$. We show it holds for $n+1$ as follows:

$$ f(n+1)=\frac{f(n)f(n-1)}{n+1}=(n+1)^{-1}\cdot \left(2^{F_{n-1}}\prod_{k=3}^{n}k^{-F_{n-k+1}}\right) \cdot \left(2^{F_{n-2}}\prod_{k=3}^{n-1}k^{-F_{n-k}}\right) $$

$$ = 2^{F_{n-1}+F_{n-2}}(n+1)^{-F_2}\cdot \left(n^{-F_1}\prod_{k=3}^{n-1}k^{-F_{n-k+1}}\right)\cdot \left(\prod_{k=3}^{n-1}k^{-F_{n-k}}\right) $$

$$ = 2^{F_n}(n+1)^{-F_2}n^{-F_1}\prod_{k=3}^{n-1}k^{-F_{n-k+1}-F_{n-k}} = 2^{F_n} \prod_{k=3}^{n+1}k^{-F_{n-k+2}} $$

$$ =2^{F_{(n+1)-1}} \prod_{k=3}^{n+1}k^{-F_{(n+1)-k+1}} $$

as required. $\blacksquare$

share|cite|improve this answer
MPW, can you please also derive this formula? – Saaqib Mahmuud Jul 29 '14 at 3:13
I will try to formulate an inductive proof and append it to my answer. It looks like it will be easy. I just wrote out the first several terms and recognized the pattern. I suggest you do so, it's rather informative. – MPW Jul 29 '14 at 3:18
@SaaqibMahmuud: I have added the inductive proof – MPW Jul 29 '14 at 4:28

As @Winther commented, letting $a_n=\log f(n)$ one has $$a_n-a_{n-1}-a_{n-2}=-\log n.$$ We only need a particular solution. Let $F_n$ be the Fibonacci sequence $F_0=F_1=1, F_i=F_{i-1}+F_{i-2}$. And consider $$b_n= \sum^n_{i=0}F_i\log (n-i).$$ It is easy to show that $$b_n=b_{n-1}+b_{n-2}+\log n.$$

share|cite|improve this answer
How is this an answer to the question? – MPW Jul 29 '14 at 4:38
MPW: It's just a different approach to your solution. Solutions to $a_n=a_{n-1}+a_{n-2}$ is classical and gives the $2^{F_n}$ part in your answer. $b_n$ here represents the product part. – Quang Hoang Jul 29 '14 at 4:43
I'm afraid I'm not following this from "We only need a particular solution" to the end. Is your answer intended to be some sort of hint? It surely isn't complete, and I'm not following it at all, sorry... – MPW Jul 29 '14 at 4:48
Yes, it was a hint. Given that $b_n=b_{n-1}+b_{n-2}+\log n$, replace $\log n$ in the relation of $a_n$'s one has $$(a_n+b_n) = (a_{n-1}+b_{n-1}) +(a_{n-1}+b_{n-1}),$$ which can be solved for any values of $a_1$ and $a_2$. – Quang Hoang Jul 29 '14 at 4:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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