Prueba de inducción fuerte: El número de Fibonacci es par si y sólo si 3 divide al índice

Question

La secuencia de Fibonacci se define recursivamente por $F_1 = 1, F_2 = 1, \; \& \; F_n = F_{n1} + F_{n2} \; \text{ for } n 3.$ Demostrar que $2 \mid F_n \iff 3 \mid n.$

Prueba por inducción fuerte : $\bbox[5px,border:1px solid green]{\color{green}{n = 1 }}$ $2 \mid F_1$ es falso. También, $3 \mid 1$ es falso.
La implicación [Falso $\iff$ Falso] es una verdad vacía.

$\bbox[5px,border:1px solid green]{\color{green}{\text{Induction Hypothesis}}}$ Supongamos que $2 \mid F_i \iff 3 \mid n$ para cada número entero $i$ con $1 i k$ .

$\bbox[5px,border:1px solid green]{\color{green}{k + 1 \text{th Case}}} \;$ Para probar: $\quad 2 \mid F_{k + 1} \iff 3 \mid k + 1.$

$\bbox[5px,border:1px solid green]{\color{green}{n = k + 1 = 2}} \;$ $2 \mid F_2$ es falso. También, $3 \mid 2$ es falso. Así que [Falso $\iff$ Falso] es una verdad vacía.

Por lo tanto, supongamos que $k + 1 3.$ Ahora consideramos tres casos:

$\bbox[5px,border:1px solid green]{\color{green}{\text{Case 1: } k + 1 = 3q}}$ Así, $3 \require{cancel}\cancel{\mid} k$ y $3 \require{cancel}\cancel{\mid} (k 1)$ . Por el ind hip, $3 \require{cancel}\cancel{\mid} k \iff F_k$ impar & $3 \require{cancel}\cancel{\mid} (k 1) \iff F_{k - 1}$ impar. Desde $F_{k+1} = F_k + F_{k1}$ Por lo tanto $F_{k+1}$ = impar + impar = incluso.

$\bbox[5px,border:1px solid green]{\color{green}{\text{Case 2: } k + 1 = 3q + 1}}$ Así, $3 | k$ y $3 \require{cancel}\cancel{\mid} (k 1).$ Por el ind hip, $3 | k \iff F_k$ incluso & $3 \require{cancel}\cancel{\mid} (k 1) \iff F_{k - 1}$ impar. Así, $F_{k+1}$ impar.

$\bbox[5px,border:1px solid green]{\color{green}{{\text{Case 3: }} k + 1 = 3q + 2}}$ Así, $3 \require{cancel}\cancel{\mid} k$ y $3 | (k 1).$ Por el ind hip, $3 \require{cancel}\cancel{\mid} k \iff F_k$ impar y $3 \mid (k 1) \iff F_{k - 1}$ incluso. Así, $F_{k+1}$ impar. $\blacksquare$

$\Large{1.}$ ¿La prueba de que el $(\Leftarrow)$ de la $(k + 1)$ ¿el caso?

$\Large{2.}$ Dado que la recursión contiene $n, n - 1, n - 2$ por lo que el "desfase" de la recursión es $3$ aquí.
Así que no debería $3$ ¿se comprueban los casos base?

$\Large{3.}$ En relación con el número 2, ¿no debería "asumir $k + 1 \geq \cancel{3} 4$ ¿"En lugar de eso"?

$\Large{4.}$ ¿No debería el $n = k + 1 = 2$ caso precede a la hipótesis de la inducción?

Me refiero a 1 . Fuente: Ejercicio 6.35, P152 de Pruebas matemáticas, 2ª ed. por Chartrand y otros

---

Suplemento a la respuesta de peterwhy:

$\Large{1.1.}$ Creí erróneamente que los 3 Casos probaban la $\Leftarrow$ . Ahora veo que el caso 1 es $\Leftarrow$ mediante una prueba directa. Los casos 2 y 3 son $\Rightarrow$ mediante una prueba por contraposición. Sin embargo, ¿cómo se puede saber/prever que se parte de $3 \mid n$ para ambos sentidos de la prueba?

Answer 1

Parte 1 El caso 1 demuestra que $3\mid (k+1)\Rightarrow 2\mid F_{k+1}$ y los casos 2 y 3 demuestran $3\cancel\mid (k+1)\Rightarrow 2\cancel\mid F_{k+1}$ . Esto último es en realidad probar el contra-positivo de $2 \mid F_{k + 1} \Longrightarrow 3 \mid k + 1$ dirección.

Parte 2 Sólo es necesario que la declaración sea verdadera para $n=k$ y $n=k-1$ para demostrar el caso de $n=k+1$ como se ve en los 3 casos. Por lo tanto, $n=1$ y $n=2$ casos son suficientes para demostrar $n=3$ caso, e iniciar el proceso de inducción.

Parte 3 :)

Parte 4 ¿Probablemente un estilo personal? Estoy de acuerdo en tener ambos $n=1$ y $n=2$ como casos base es más atractivo para mí.

Answer 2

Mira $F_n$ modulo $2$ . Encontrarás el patrón de congruencias: $$1, 1, 0, 1, 1, 0, ...$$ . Esto se deduce del hecho de que $F_1 \equiv F_2 \equiv 1$ (mod $2$ ) y la definición recursiva de los números de Fibonnaci.

Answer 3

Desde el período de $2$ en la base $\phi^2$ es de tres plazas = $0.10\phi\; 10\phi \dots$ y los números de fibonacci representan los repuntes de base $\phi^2$ entonces se deduce que $2$ divide uno de cada tres números de fibonacci, de la misma manera que $37$ divide cada tres repuntes en decimales (es decir $111$ , $111111$ , $111111111$ etc.).