*19. Demonstre que f_{k} f_{n}+f_{k+1} f_{n+1}=f_{n+k+1} para todos os números inteiros não negativos n, em que k é um número inteiro não negativo e f_{i} indica o i-ésimo número de Fibonacci.

Passo 1

O enunciado pede para provar que, para quaisquer inteiros não negativos k e n, vale
f_k\,f_n \;+\; f_{k+1}\,f_{n+1} \;=\; f_{n+k+1},
sendo \{f_i\} a sequência de Fibonacci definida por
f_0 = 0,\quad f_1 = 1,\quad f_{m+2} = f_{m+1} + f_m.
O método mais direto é usar prova por indução em k, deixando n livre.

Passo 2

Base da indução k=0. Nesse caso
f_0\,f_n + f_1\,f_{n+1} = 0\cdot f_n + 1\cdot f_{n+1} = f_{n+1},
enquanto o lado direito é
f_{n+0+1} = f_{n+1}.
Logo, para k=0 a identidade vale para todo n.

Passo 3

Passo indutivo. Suponha que, para algum inteiro k\ge0, valha
f_k\,f_n + f_{k+1}\,f_{n+1} = f_{n+k+1} \quad\text{para todo \(n\).}

Passo 4

Precisamos mostrar que então
f_{k+1}\,f_n + f_{k+2}\,f_{n+1} \;=\; f_{n+(k+1)+1}.
Usando a relação de Fibonacci f_{k+2} = f_{k+1} + f_k e f_{n+2}=f_{n+1}+f_n, calculamos o lado esquerdo:
\begin{aligned} f_{k+1}\,f_n + f_{k+2}\,f_{n+1} &= f_{k+1}\,f_n + (f_{k+1}+f_k)\,f_{n+1}\\\ &= f_{k+1}(f_n+f_{n+1}) + f_k\,f_{n+1}\\\ &= f_{k+1}\,f_{n+2} + f_k\,f_{n+1}. \end{aligned}
Mas pela hipótese de indução, para o mesmo k e n substituído por n+1, temos
f_k\,f_{n+1} + f_{k+1}\,f_{n+2} = f_{(n+1)+k+1} = f_{n+k+2}.
Portanto
f_{k+1}\,f_n + f_{k+2}\,f_{n+1} = f_{n+k+2} = f_{n+(k+1)+1},
como queríamos.

Resposta

Por indução em k, mostramos que para todo inteiro k\ge0 e todo n\ge0 vale
f_k\,f_n + f_{k+1}\,f_{n+1} = f_{n+k+1}.

Exercícios de Livros Relacionados