Resolviendo la relación de recurrencia: Forma del producto

Question

Por favor, ayuden a encontrar la solución de esta recursividad.

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

donde $ f(1)=1$ y $f(2)=2$ .

Answer 1

Toma un poco de n grande, $$ \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} $$ en cada paso hasta que el "..." Acabo de enchufar la fórmula en el factor izquierdo del numerador hasta que vi un patrón. El símbolo $F_n$ denota la secuencia de Fibonacci, que sigue $F_n = F_{n-1} + F_{n-2}$ y $F(0) = 0$ y $F(1) = 1$ . Lo siento, esto no es una prueba formal, pero se puede probar fácilmente por inducción demostrando que, si es cierto para alguna n grande, entonces debe ser cierto para n+1, y luego simplemente demostrando que es cierto para 3.

Answer 2

Creo que la fórmula es, para $n \geq 3$ ,

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

donde $F_1,F_2,F_3, \ldots $ es la secuencia estándar de Fibonacci cuyos dos primeros términos son $1$ .

Puedes ver esto con sólo escribir los primeros términos. Por ejemplo,

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

Adición (Prueba inductiva): El caso base ( $n=3$ ) es trivial, ya que $$f(3)= \dfrac {f(2)f(1)}3= \dfrac {2 \cdot 1}3 = \frac23 =2^1 3^{-1}=2^{F_2}3^{-F_1}$$

Para el paso inductivo, supongamos que la fórmula se mantiene para $3, \ldots ,n$ . Mostramos que se mantiene para $n+1$ de la siguiente manera:

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

como se requiere. $ \blacksquare $

Answer 3

Como @Winther comentó, dejar $a_n= \log f(n)$ uno tiene $$a_n-a_{n-1}-a_{n-2}=- \log n.$$ Sólo necesitamos una solución particular. Deje que $F_n$ ser la secuencia de Fibonacci $F_0=F_1=1, F_i=F_{i-1}+F_{i-2}$ . Y considera $$b_n= \sum ^n_{i=0}F_i \log (n-i).$$ Es fácil mostrar que $$b_n=b_{n-1}+b_{n-2}+ \log n.$$