Prueba de Fibonacci derivación

Question

Me preguntaba cómo probar que

$$f(n+m+2) = f(n+1)f(m+1) + f(n)f(m)$$

donde $f$ es la secuencia de fibonacci y n, m son números enteros positivos.

Puede ser este hecho con la inducción?

Estoy perdido con este método de prueba, debido a que hay dos variables.

Cualquier idea o sugerencia es bienvenida.

Answer 1

Puede ser este hecho con la inducción?

Se puede. Más específicamente, se puede hacer con una fuerte inducción de dos variables. Primero, sugiero mirar http://math.stackexchange.com/a/7665/146030 y pensando en por qué, en ambos casos, los primeros tres declaraciones que implica el cuarto.

Vamos a probar la afirmación de que

$$f(n+m+2)=f(n+1)f(m+1)+f(n)f(m).$$

Para empezar podemos definir la secuencia de fibonacci como

\begin{align} f(0)&=0 \\ f(1)&=1 \\ f(n)&=f(n-1)+f(n-2), \text{for } n\ge2. \end{align}

Al $n=0$ $m=0$

\begin{align} f(n+m+2) &= f(2) \\ &= 1 \\ &= 1 \cdot1 + 0\cdot0 \\ &= f(1)f(1)+f(0)f(0) \\ &= f(n+1)f(m+1)+f(n)f(m) \end{align}

y así la afirmación es verdadera cuando $n=m=0$.

Para demostrar la declaración de la verdad para todos no negativos $n,m$, primero se introducirá en $n=k$ fijos $m$. Supongamos que la instrucción verdadera para todos los $0\leq k\leq n$. Ahora podemos probar la declaración de $k+1$.

\begin{align} f((k+1)+m+2) &= f(k+m+3) \\ &= f(k+m+2) + f(k+m+1) \\ &= f(k+m+2) + f((k-1)+m+2) \\ &= \big[f(k+1)f(m+1)+f(k)f(m)\big] + \big[f(k)f(m+1)+f(k-1)f(m)\big] \\ &= \big[f(k+1)f(m+1)+f(k)f(m+1)\big] + \big[f(k)f(m)+f(k-1)f(m)\big] \\ &= \big[f(k+1)+f(k)\big]f(m+1) + \big[f(k)+f(k-1)\big]f(m) \\ &= f(k+2)f(m+1) + f(k+1)f(m) \\ &= f((k+1)+1)f(m+1) + f(k+1)f(m) \end{align}

Y, entonces, por inducción matemática que la afirmación es verdadera para todos los $n$ y que fija $m$. Podemos ver que una similar inductivo prueba de obras por un determinado $n$$m=k$. Por lo tanto podemos concluir que la afirmación es verdadera.