Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
I tried that already..But it blocks the way of further thinking –  Rejo_Slash Jul 29 at 2:38
    
What have you tried? –  anorton Jul 29 at 2:50
    
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 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 at 2:56

3 Answers 3

up vote 3 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|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|improve this answer
    
MPW, can you please also derive this formula? –  Saaqib Mahmuud Jul 29 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 at 3:18
    
@SaaqibMahmuud: I have added the inductive proof –  MPW Jul 29 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|improve this answer
    
How is this an answer to the question? –  MPW Jul 29 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 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 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 at 4:51

Your Answer

 
discard

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.