# Solving recurrence relation: Product form

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

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

-
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

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.

-

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$

-
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.$$

-
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