*17. Determine quais números de Fibonacci são pares e use uma forma da indução matemática para demonstrar sua conjectura.
Passo 1
O enunciado quer saber quais termos da sequência de Fibonacci são pares e pede para provar essa propriedade por indução. A sequência de Fibonacci é definida por
Passo 2
Vamos listar os primeiros termos e ver onde aparecem os pares:
(ímpar),
(ímpar),
(par),
(ímpar),
(ímpar),
(par),
(ímpar),
(ímpar),
(par),
(ímpar),
(ímpar),
(par), …
Os índices dos termos pares são
Os índices dos termos pares são
Passo 3
Conjectura:
“ é par se, e somente se,
divide
.”
Ou seja, é par exatamente quando
para algum
.
“
Ou seja,
Passo 4
Prova por indução forte em
:
Base
:
- Para
e , temos e ímpares, e , . - Para
, é par e .
Passo indutivo: suponha que, para todo
, vale
“ é par
.”
Para , use a relação de recorrência:
“
Para
Pela hipótese,
-
é par , -
é par .
Agora analisamos os três casos de
módulo 3:
Caso 1:
.
Então e
, logo
e
são ímpares.
Então
e
.
Caso 2:
.
Então e
, logo
é par e
é ímpar.
Então
e
.
Caso 3:
.
Então e
, logo
é ímpar e
é par.
Então
e
.
Em cada caso provamos que
Isso conclui a indução.