Prove por indução que para todo
:
Identifique as regras de inferência usadas na demonstração.
Passo 1
O que o enunciado pede e o que temos disponível.
- Pede-se provar que, para todo
,
- Também pede-se identificar as regras de inferência usadas na demonstração.
Informações relevantes extraídas do enunciado:
- A soma
é a soma dos inteiros de até . - A prova deve ser por indução matemática, isto é, devemos mostrar uma base e um passo indutivo que permita concluir que a propriedade vale para todo
.
Passo 2
Definir a propriedade
que será usada na indução.
- Defino a fórmula proposicional parametrizada por
:
- Objetivo: provar
.
Vou usar a estrutura padrão da prova por indução: (i) prova da base
; (ii) prova do passo indutivo
; (iii) aplicar o princípio da indução para concluir
.
Passo 3
Provar a base:
.
- Calculo o lado esquerdo para
:
- Calculo o lado direito para
:
- Conclusão: os dois lados são iguais, logo
é verdadeira.
Comentário didático: aqui fiz uma verificação direta por cálculo aritmético simples; esse tipo de passo usa a regra de igualdade (introdução/eliminação de igualdade e cálculo aritmético baseado nos axiomas da aritmética).
Passo 4
Preparar o passo indutivo: assumir a hipótese indutiva.
- Tome um
arbitrário e suponha (hipótese indutiva) que seja verdadeira, isto é, suponha
- Aviso didático: esta suposição é temporária — é o que se faz numa prova por implicação (prova condicional). Fizemos uma suposição para deduzir algo subsequente e, depois, retirar a suposição para obter a implicação
.
Passo 5
Expressar a soma até
em função da soma até
.
- Pela definição da soma finita,
- Comentário: isto é uma propriedade imediata da soma indexada: somar até
é somar até e depois adicionar o termo .
Passo 6
Usar a hipótese indutiva (substituição) para substituir a soma
.
- Pela hipótese indutiva,
. Substituo na igualdade do Passo 5:
- Regra usada aqui: substituição por igualdade (às vezes chamada de regra de substituição ou princípio de Leibniz): se
então em qualquer expressão onde aparece pode-se substituir por .
Passo 7
Fazer a manipulação algébrica para obter a forma desejada.
- Parto da expressão obtida:
- Coloco em evidência o fator
:
- Somo as frações dentro do parêntese:
- Logo
- Observação:
, portanto posso escrever
Passo 8
Concluir o passo indutivo:
.
- A partir do Passo 6 e Passo 7 obtivemos
ou seja,
é verdadeira sob a hipótese
.
- Portanto, para o
arbitrário escolhido, a implicação foi demonstrada. - Regra lógica utilizada: prova condicional (implication introduction). Assumiu-se
e a partir disso deduziu-se ; então conclui-se .
Passo 9
Aplicar o princípio da indução matemática e concluir para todo
.
- Tendo provado (i)
(Passo 3) e (ii) (pela arbitrariedade de no Passo 8 podemos generalizar para todo ), aplica-se o princípio da indução matemática para concluir
isto é,
- Comentário didático: o princípio da indução é a regra que permite, a partir da base e do passo indutivo (a implicação para um
arbitrário), deduzir que a propriedade vale para todos os naturais. Em lógica formal, essa é uma regra/axioma aceita sobre os números naturais.
Passo 10
Resumo das regras de inferência e operações usadas na prova e onde foram aplicadas.
- Definição/propriedade de soma indexada: usada no Passo 5 para escrever
. - Verificação direta / cálculo aritmético: usada no Passo 3 para mostrar
. - Assunção temporária (técnica de prova condicional): no Passo 4 supôs-se
para derivar . - Substituição por igualdade (princípio de Leibniz): no Passo 6 substituiu-se
por . - Manipulação algébrica / propriedades da aritmética (fatoração, soma de frações): no Passo 7 para transformar a expressão e obter a forma desejada.
- Introdução da implicação (conditional proof): ao retirar a suposição e concluir
no Passo 8. - Generalização universal: como
era arbitrário, generalizou-se a implicação para . - Princípio da indução matemática: a partir de
e de concluiu-se .
Resposta
Regras de inferência usadas: definição da soma indexada; verificação direta (cálculo aritmético); assunção temporária para prova condicional; substituição por igualdade (Leibniz); manipulação algébrica; introdução da implicação (conditional proof); generalização universal; princípio da indução matemática.