Exercício 34. Prove por indução a propriedade de Fibonacci:
F_{1}+F_{2}+\cdots+F_{n}=F_{n+2}-1
Identifique o uso do silogismo disjuntivo na definição recursiva.

Passo 1

O enunciado pede duas coisas:
  1. Provar por indução a igualdade F_{1}+F_{2}+\cdots+F_{n}=F_{n+2}-1
para todo n natural adequado (vamos entender n\ge1).
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):
  • F_{1}=1.
  • F_{2}=1.
  • Para n\ge3, F_{n}=F_{n-1}+F_{n-2}.
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:
  • Base(s): verificar que a afirmação vale para os primeiros valor(es) de n (por exemplo n=1, às vezes também n=2 se a recorrência usar dois primeiros termos).
  • Passo indutivo: assumir que a afirmação vale para um k arbitrário (hipótese de indução) e mostrar que disso segue que vale para k+1. Se essas duas etapas funcionarem, a afirmação vale para todo n na gama considerada.
Vamos aplicar isto ao nosso problema.

Passo 3

Base da indução — verificar para n=1 e n=2. (Aqui é conveniente checar os dois porque a definição de Fibonacci dá dois primeiros termos explícitos.)
  • Caso n=1: a soma do lado esquerdo é só F_{1}. Então calculamos
F_{1} = 1.
O lado direito é
F_{1+2}-1 = F_{3}-1.
Mas F_{3}=F_{2}+F_{1}=1+1=2 (pela definição recursiva aplicada a n=3), então
F_{3}-1 = 2-1 = 1.
Portanto para n=1 temos F_{1}=F_{3}-1, ou seja a igualdade vale.
  • Caso n=2: o lado esquerdo é F_{1}+F_{2}=1+1=2. O lado direito é
F_{2+2}-1 = F_{4}-1.
Calculamos F_{4}=F_{3}+F_{2}=(F_{2}+F_{1})+F_{2}=(1+1)+1=3, então
F_{4}-1 = 3-1 = 2.
Logo para n=2 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 k\ge2 qualquer a afirmação seja verdadeira, isto é suponha que
F_{1}+F_{2}+\cdots+F_{k}=F_{k+2}-1.
Esta é a hipótese que vamos usar para provar a afirmação para n=k+1.

Passo 5

Passo indutivo — mostrar que a hipótese implica a fórmula para k+1.
Começamos pela soma até k+1 e usamos a propriedade básica de somas (adicionar o último termo):
F_{1}+F_{2}+\cdots+F_{k}+F_{k+1}=\bigl(F_{1}+F_{2}+\cdots+F_{k}\bigr)+F_{k+1}.
Pelo que assumimos na hipótese de indução, podemos substituir a soma até k por F_{k+2}-1. Assim
\bigl(F_{1}+F_{2}+\cdots+F_{k}\bigr)+F_{k+1} = \bigl(F_{k+2}-1\bigr)+F_{k+1}.
Agrupando os termos:
F_{k+2}-1 + F_{k+1} = \bigl(F_{k+2}+F_{k+1}\bigr) - 1.
Agora usamos a definição recursiva de Fibonacci para combinar F_{k+2} e F_{k+1}. A definição diz que, para índices \ge3,
F_{m+1}=F_{m}+F_{m-1}.
Aplicando com m=k+2 (observe que k+2\ge3 pois k\ge1), obtemos
F_{k+3}=F_{k+2}+F_{k+1}.
Substituindo isto na expressão anterior:
\bigl(F_{k+2}+F_{k+1}\bigr)-1 = F_{k+3}-1.
Portanto chegamos a
F_{1}+F_{2}+\cdots+F_{k}+F_{k+1}=F_{k+3}-1,
que é exatamente a formula com n=k+1 (porque k+1+2=k+3). Assim mostramos que a hipótese para k implica o caso k+1.

Passo 6

Conclusão da indução: como verificamos as bases n=1 e n=2 e provamos que, para todo k\ge2, a validade para k implica a validade para k+1, a propriedade vale para todo n\ge1. Ou seja provamos por indução que
F_{1}+F_{2}+\cdots+F_{n}=F_{n+2}-1
para todo n natural (com n\ge1).
Exemplo numérico rápido para sentir a fórmula: para n=4,
F_{1}+F_{2}+F_{3}+F_{4}=1+1+2+3=7,
enquanto
F_{4+2}-1=F_{6}-1=8-1=7,
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:
  • Se n=1 ou n=2 então F_{n}=1.
  • Caso contrário (isto é, se nem n=1 nem n=2) então F_{n}=F_{n-1}+F_{n-2}.
Essa forma é uma definição por disjunção de casos. O uso do silogismo disjuntivo aparece quando, para um dado n, decide-se qual caso usar. Formalmente: da disjunção
(n=1)\\ \lor\\ (n=2)\\ \lor\\ (n\ge3)
e das negações de dois disjuntos (por exemplo \neg(n=1) e \neg(n=2)) conclui-se n\ge3. 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 F_{5} diz-se: ou 5=1 ou 5=2 ou 5\ge3; como não é nem 1 nem 2, conclui-se que vale a terceira alternativa e aplica-se F_{5}=F_{4}+F_{3}. Esse raciocínio é um uso explícito do silogismo disjuntivo.

Resposta

F_{1}+F_{2}+\cdots+F_{n}=F_{n+2}-1\quad\text{para todo }n\ge1.
O silogismo disjuntivo aparece na definição recursiva na forma de casos: (n=1)\lor(n=2)\lor(n\ge3); ao rejeitar n=1 e n=2 conclui-se n\ge3 e aplica-se F_{n}=F_{n-1}+F_{n-2}.

Exercícios relacionados