Cuando tengo 2 variables y 2 casos base, ¿puedo utilizar la inducción matemática varias veces para formar una prueba?

Question

Mi libro de texto me pide que demuestre esta afirmación sobre los números de Fibonacci:

$$F_{m+n} = F_{m} F_{n+1} + F_{m-1} F_{n}, \qquad \text{given that }m \geq 1, n \geq 0.$$

TL,DR : ¿Puedo demostrarlo por inducción matemática sobre m, y luego sobre n, por separado?

---

Con más detalle:

Creo que se supone que debo expandir esto usando la ecuación de forma cerrada $$F_k = \frac{\varphi^k - \hat\varphi^k}{\sqrt{5}}$$

ya que al fin y al cabo de eso trata el capítulo, pero no puedo evitar sentir que si hiciera la siguiente variante de la inducción matemática,

• Demostrar el caso base en el que $m=1$ y $n=0$ ,
• Demostrar que el caso de $m, n=0$ implica el caso de $m+1, n=0$ y
• Demostrar que el caso de $m=1, n$ implica el caso de $m=1, n+1$ .

Todavía tendría una prueba válida en mis manos. He demostrado que los casos pueden expandirse "hacia fuera" en dos direcciones, por así decirlo, y por tanto deberían poder componerse juntos para demostrar que el $m, n$ implica el $m+1, n+1$ caso en general.

Por otro lado, siento que hay una sutileza que hace que eso no sea una buena estrategia que no estoy viendo aquí. Como "sé" que existe una prueba (porque este es un problema de libro de texto), hacer eso sin entender si se aplica en general podría ser un paso en falso.

Answer 1

La forma más clara de mostrarlo es utilizar las matrices \begin{eqnarray*} \begin{bmatrix} 0 &1 \\1 &1 \\ \end{bmatrix} ^m = \begin{bmatrix} F_{m-1} &F_m \\F_m &F_{m+1} \\ \end{bmatrix} . \ y el resto del mundo \begin{eqnarray*} \begin{bmatrix} 0 &1 \\1 &1 \\ \end{bmatrix} ^n = \begin{bmatrix} F_{n-1} &F_n \\F_n &F_{n+1} \\ \end{bmatrix} . \N - Fin. Así que \begin{eqnarray*} \begin{bmatrix} F_{m+n-1} &F_{m+n} \\F_{m+n} &F_{m+n+1} \\ \end{bmatrix} = \begin{bmatrix} 0 &1 \\1 &1 \\ \end{bmatrix}^{n+m} = \begin{bmatrix} 0 &1 \\1 &1 \\ \end{bmatrix}^{m} \begin{bmatrix} 0 &1 \\1 &1 \\ \end{bmatrix}^{n} \\ \begin{bmatrix} F_{m-1} &F_m \\F_m &F_{m+1} \\ \end{bmatrix} \begin{bmatrix} F_{n-1} &F_n \\F_n &F_{n+1} \\ \end{bmatrix} = \begin{bmatrix} . &F_{m-1}F_n+F_m F_{n+1} \\. & . \\ \end{bmatrix} . \ y el resto del mundo

Answer 2

Tu doble inducción no es suficiente tal y como lo has planteado. Acabas demostrando sólo los casos con $n=0$ y arbitraria $m$ y con $m=1$ y arbitraria $n$ .

Además, aunque no estoy seguro de que realmente estés tratando de hacer esto, pero casi suena como si quisieras ir de la $(m,n)$ caso directamente a la $(m+1,n+1)$ caso, pero eso no sería correcto, ya que ahora sólo se golpea el $(1,0)$ , $(2,1)$ , $(3,2)$ ... casos. Está claro que se quiere llegar a todos los casos del conjunto $m \times n$ de la rejilla, en lugar de sólo su diagonal.

En cambio, lo que podrías hacer es pasar de la $(m,n)$ caso tanto a la $(m,n+1)$ caso y el $(m+1,n)$ caso.

Otra cosa a tener en cuenta, sin embargo, es que estás tratando con los números de Fibonacci, y donde una inducción de una sola variable que involucra a los números de Fibonacci implica tener dos casos base, con este tipo de inducción doble realmente necesitarás todos esos casos con $n=0$ y arbitraria $m$ y todos los casos con $m=1$ y arbitraria $n$ como sus casos base, para que pueda pasar de la $(m-1,n)$ y el $(m,n)$ caso a la $(m+1,n)$ caso, y del $(m,n-1)$ y el $(m,n)$ caso a la $(m,n+1)$ caso.

Eso es:

Suponga que ha demostrado (por inducción) que la afirmación es verdadera para todos los casos con $n=0$ y arbitraria $m$ y con $m=1$ y arbitraria $n$ .

Así que ahora toma un poco de arbitrariedad $m > 1, n > 0$

Asumir la hipótesis inductiva:

$$F_{m+n} = F_{m} F_{n+1} + F_{m-1} F_{n}$$

y:

$$F_{m+n-1} = F_{m} F_{n} + F_{m-1} F_{n-1}$$

y:

$$F_{m-1+n} = F_{m-1} F_{n+1} + F_{m-2} F_{n}$$

Primero hacer $m,n+1$ :

$$F_{m+(n+1)} = F_{m+n-1}+ F_{m+n} \overset{Inductive Hypothesis}{=}$$

$$ F_{m} F_{n} + F_{m-1} F_{n-1} + F_{m} F_{n+1} + F_{m-1} F_{n}=$$

$$ F_{m} (F_{n} + F_{n+1}) + F_{m-1} (F_{n-1} + F_{n})=$$

$$ F_{m} F_{n+2} + F_{m-1} F_{n+1}$$

como se desee.

Ahora haz $m+1,n$ :

$$F_{m+1+n} = F_{m-1+n}+ F_{m+n} = \overset{Inductive Hypothesis}{=}$$

$$F_{m-1} F_{n+1} + F_{m-2} F_{n} + F_{m} F_{n+1} + F_{m-1} F_{n}=$$

$$(F_{m-1} + F_{m}) F_{n+1} + (F_{m-2} + F_{m-1})F_{n} =$$

$$F_{m+1} F_{n+1} + F_{m}F_{n}$$

De nuevo, como se desee.

... bueno, vale, eso funciona, pero requería infinitos casos base, que requerían su propia inducción. ¿No hay algo que podamos hacer para evitar esto? Sí.

Aquí hay algo que puedes hacer. Haz la inducción en $k$ , donde $k=m+n$ . Es decir, demostrar que la afirmación es válida para $(1,0)$ , $(1,1)$ y $(2,0)$ como sus casos base, y luego mostrar que para cualquier $k>2$ si suponemos que la afirmación es válida para todos los $(m,n)$ con $m+n=k-2$ y la afirmación también es válida para todos los $(m,n)$ con $m+n=k-1$ entonces la afirmación también es válida para todo $(m,n)$ con $m+n=k$ . Ahora, al probar este paso, tendrás que tener en cuenta los casos límite en los que $m=1$ o donde $n=0$ sin embargo, pero aparte de eso se pueden seguir las derivaciones anteriores, por lo que parecería ser un poco menos de trabajo.

Por último, he aquí un método para demostrar la afirmación sin ninguna inducción difícil. Supongamos que queremos subir unas escaleras y que en cada escalón podemos subir uno o dos escalones: ¿de cuántas maneras podemos subir las escaleras? Bien, si decimos que hay $n-1$ escaleras, entonces resulta que hay $F_n$ formas de hacerlo (donde $F_0$ se define como $0$ y $F_1$ à $1$ ). He aquí la razón: para su primer paso puede ir uno arriba o dos arriba. Ahora bien, si por hipótesis inductiva hay $F_{n-1}$ formas de terminar de escalar el $n-2$ escaleras después de haber dado un paso de $1$ escaleras, y hay $F_{n-2}$ formas de terminar de escalar el $n-3$ escaleras después de haber dado un paso de $2$ escaleras, entonces se deduce que hay $F_{n-1}+F_{n-2}=F_n$ formas de escalar el original $n-1$ escaleras, completando la prueba inductiva de que efectivamente hay $F_n$ formas de escalar $n-1$ escaleras si cada paso que das $1$ o $2$ escaleras.

Vale, pero eso significa que podemos subir $m+n-1$ escaleras en $F_{m+n}$ formas. Pero atención: podemos subir las escaleras y en algún momento habiendo subido exactamente $m-1$ escaleras, o podemos subir las escaleras y en algún momento haber subido exactamente $m-2$ escaleras, tras lo cual damos un paso de dos escaleras, y continuamos nuestro camino: cada forma de subir las escaleras se hará de una de esas dos maneras diferentes. Bien, pero la primera forma puede hacerse en $F_m F_{n+1}$ maneras, ya que se puede subir $m-1$ pasos en $F_m$ maneras y luego terminar el otro $n$ escaleras en $F_{n+1}$ formas. Para el segundo método hay $F_{m-1}$ formas de subir por primera vez $m-2$ escaleras, y luego $F_n$ formas de escalar lo que queda $n-1$ escaleras después de dar un paso de dos escaleras después, para un total de $F_{m-1}F_n$ formas. Por lo tanto, debe ser cierto que:

$$F_{m+n} = F_{m} F_{n+1} + F_{m-1} F_{n}$$

Answer 3

El truco que he aprendido para la doble inducción es hacer tu caso base $m=0$ y $n=0$ y luego arreglar $n$ a un valor arbitrario (suelo empezar fijando el segundo), y luego hacer la inducción en $m$ . Entonces arregla $m$ a un valor arbitrario y hacer la inducción sobre $n$ . Una vez hecho esto sabes que para cualquier valor de $n$ su afirmación es válida para todos $m$ y para cualquier valor de $m$ su almeja se mantiene para todos $n$ . Esto debería ser suficiente para demostrar que su afirmación es válida para cada $(m,n)$ par.

Answer 4

Sí, se puede hacer esa "doble inducción". Hay múltiples formas de hacerlo, y la tuya parece ser válida.

Sin embargo, a menudo no es necesario hacer dos inducciones, sino que basta con decir "Fijar un $m$ " y luego hacer una inducción en $n$ . Esencialmente estás haciendo una inducción (en $n$ ) que tiene un parámetro ( $m$ ), pero su prueba es válida independientemente del valor de $m$ .

Para tu problema, no necesitas hacer el segundo paso de la viñeta - si introduces $n = 0$ se obtiene una declaración verdadera independientemente del valor de $m$ . Esta observación sirve como caso base (para todos los valores posibles de $m \gt 0$ ). Ahora sólo haz tu tercer paso, que es una inducción en $n \rightarrow n+1$ y ya está. (Por cierto, no creo que tengas que recurrir a la forma cerrada, creo que puedes salirte con la tuya utilizando la fórmula estándar de recursión de Fibonacci. Pero en realidad no lo he resuelto, así que no estoy seguro).

Answer 5

El proceso siguiente es bastante revelador si se tiene en cuenta la secuencia de Fibonacci

$$\begin{array}{ccccccc}F_1&F_2&F_3&F_4&F_5&F_6&\ldots\\1&1&2&3&5&8&\ldots\end{array}$$

y nos centramos en los coeficientes de los lados de la derecha:

$$\begin{align} F_k&=1F_{k-2}+1F_{k-1}\tag{write $F_{k-1}=F_{k-3}+F_{k-2}$}\\ &=1F_{k-3}+2F_{k-2}\tag{write $F_{k-2}=F_{k-4}+F_{k-3}$}\\ &=2F_{k-4}+3F_{k-3}\tag{write $F_{k-3}=F_{k-5}+F_{k-4}$}\\ &=3F_{k-5}+5F_{k-4}\tag{write $F_{k-4}=F_{k-6}+F_{k-5}$}\\ &=5F_{k-6}+8F_{k-5}\tag{etc.}\\& \phantom{a}\vdots\end{align}$$

Es natural hacer conjeturas:

$$F_k=c_mF_{k-m}+d_{m+1}F_{k-m+1}$$

con $c_m=F_{m-1}$ y $d_{m+1}=c_{m+1}=F_m$ para que:

$$F_{k}=F_{m-1}F_{k-m}+F_mF_{k-m+1}$$

Pero no sólo eso, sino que a partir de este proceso podemos ver directamente cómo utilizar la inducción para demostrar que los coeficientes $c_m$ obedecen a la recurrencia de Fibonacci.

Si finalmente definimos $n$ como $k=n+m$ entonces obtenemos su resultado:

$$F_{n+m}=F_{m-1}F_n+F_mF_{n+1}\tag*{}$$