A indução é necessária para este argumento?

Question

Esta pergunta é sobre o Exercício 13 da Seção 1-1 da Teoria dos Números de George E. Andrews. O livro diz:

Os números Lucas $L_n$ são definidos pelas equações $L_1 = 1$e $L_n = F_{n + 1} + F_{n - 1}$ para cada $n \geq 2$. Nós também temos isso

$\textbf{Claim: }\ L_n = L_{n - 1} + L_{n - 2}\ \text{ for }\ n \geq 3$.

$\textit{My attempt at a proof: }$Abordamos por indução matemática. Para o caso básico, considere quando$n = 3$. Nós temos isso$L_3 = F_4 + F_2 = 3 + 1 = (2 + 1) + 1 = (F_3 + F_1) + 1 = L_2 + L_1$ então, a reivindicação se mantém quando $n = 1$. Agora, suponha que a afirmação seja válida para um inteiro$k > 1$. Então,\begin{align*} L_{k + 1} &= F_{k + 2} + F_k && \text{definition of Lucas number}\\ &= (\underline{F_k} + \underline{\underline{F_{k + 1}}}) + (\underline{F_{k - 2}} + \underline{\underline{F_{k - 1}}}) && \text{Fibonacci recurrence}\\ &= L_{k - 1} + L_k && \text{definition of Lucas number}. \end{align*} Portanto, a reivindicação também vale para o inteiro $k + 1$. Pelo princípio da indução matemática, a afirmação vale para todos$n \geq 3$.

O problema que estou tendo é que não usei a hipótese indutiva. Então, estou confuso se minha prova está errada ou se o argumento não requer indução, etc.

Fiz uma pesquisa rápida e parece que os números de Lucas são geralmente definidos por $L_0 = 2$, $L_1 = 1$e $L_n = L_{n - 1} + L_{n - 2}$ para $n \geq 3$. E o problema geralmente é mostrar$L_n = F_{n + 1} + F_{n - 1}$ para cada $n \geq 2$. Isso seria um erro de digitação no livro ou um mal-entendido da minha parte?

Answer 1

Você está correto quando diz que sua prova não usa indução. É um argumento direto usando a definição dada para os números de Lucas e a propriedade dos números de Fibonacci.

A conclusão é que os números de Lucas e Fibonacci satisfazem a mesma condição recursiva.

Então, para recuperar a definição que você encontrou para os números de Lucas, você precisa apenas verificar as condições originais.

Como as definições são de fato equivalentes, não há razão para supor que haja um erro de digitação no livro.