Exercício 34. Prove por indução a propriedade de Fibonacci:
Identifique o uso do silogismo disjuntivo na definição recursiva.
Passo 1
O enunciado pede duas coisas:
- Provar por indução a igualdade
para todo
natural adequado (vamos entender
).
2. Identificar onde aparece o uso do silogismo disjuntivo na definição recursiva dos números de Fibonacci.
2. Identificar onde aparece o uso do silogismo disjuntivo na definição recursiva dos números de Fibonacci.
Informações dadas (definição de Fibonacci que vamos usar — peguei isto do enunciado implícito):
-
. -
. - Para
, .
Estas são todas as informações relevantes; a prova pedida é uma prova por indução matemática do enunciado acima e depois uma observação lógica sobre a forma da definição recursiva.
Passo 2
Explicando rapidamente o que é prova por indução (aula rápida e prática):
A indução matemática tem duas etapas essenciais:
A indução matemática tem duas etapas essenciais:
- Base(s): verificar que a afirmação vale para os primeiros valor(es) de
(por exemplo , às vezes também se a recorrência usar dois primeiros termos). - Passo indutivo: assumir que a afirmação vale para um
arbitrário (hipótese de indução) e mostrar que disso segue que vale para . Se essas duas etapas funcionarem, a afirmação vale para todo na gama considerada.
Vamos aplicar isto ao nosso problema.
Passo 3
Base da indução — verificar para
e
. (Aqui é conveniente checar os dois porque a definição de Fibonacci dá dois primeiros termos explícitos.)
- Caso
: a soma do lado esquerdo é só . Então calculamos
O lado direito é
Mas
(pela definição recursiva aplicada a
), então
Portanto para
temos
, ou seja a igualdade vale.
- Caso
: o lado esquerdo é . O lado direito é
Calculamos
, então
Logo para
a igualdade também vale.
Ter as duas bases verificadas dá segurança para usar a recorrência que envolve dois termos anteriores.
Passo 4
Hipótese de indução: suponha que para um
qualquer a afirmação seja verdadeira, isto é suponha que
Esta é a hipótese que vamos usar para provar a afirmação para
.
Passo 5
Passo indutivo — mostrar que a hipótese implica a fórmula para
.
Começamos pela soma até
e usamos a propriedade básica de somas (adicionar o último termo):
Pelo que assumimos na hipótese de indução, podemos substituir a soma até
por
. Assim
Agrupando os termos:
Agora usamos a definição recursiva de Fibonacci para combinar
e
. A definição diz que, para índices
,
Aplicando com
(observe que
pois
), obtemos
Substituindo isto na expressão anterior:
Portanto chegamos a
que é exatamente a formula com
(porque
). Assim mostramos que a hipótese para
implica o caso
.
Passo 6
Conclusão da indução: como verificamos as bases
e
e provamos que, para todo
, a validade para
implica a validade para
, a propriedade vale para todo
. Ou seja provamos por indução que
para todo
natural (com
).
Exemplo numérico rápido para sentir a fórmula: para
,
enquanto
coincide — bom sinal!
Passo 7
Identificação do silogismo disjuntivo na definição recursiva (aula curta de lógica aplicada):
A definição recursiva costuma ser dada em forma de casos:
A definição recursiva costuma ser dada em forma de casos:
- Se
ou então . - Caso contrário (isto é, se nem
nem ) então .
Essa forma é uma definição por disjunção de casos. O uso do silogismo disjuntivo aparece quando, para um dado
, decide-se qual caso usar. Formalmente: da disjunção
e das negações de dois disjuntos (por exemplo
e
) conclui-se
. Este passo — da disjunção e das negações de alguns disjuntos inferir o disjunto restante — é exatamente o padrão do silogismo disjuntivo (ou sua forma estendida para três disjuntos). Na prática, ao calcular
diz-se: ou
ou
ou
; como não é nem 1 nem 2, conclui-se que vale a terceira alternativa e aplica-se
. Esse raciocínio é um uso explícito do silogismo disjuntivo.
Resposta
O silogismo disjuntivo aparece na definição recursiva na forma de casos:
; ao rejeitar
e
conclui-se
e aplica-se
.