LFCOMP

1ª)
a) Prova por Indução Método usado para mostrar que todos os elementos de um conjunto infinito têm uma propriedade específica a partir de um caso usado como base. Assim que provado para um caso base, a regra de indução é usada para provar uma serie de outros casos, geralmente infinitos.
Seja P uma propriedade e N os números naturais. Para provar que P(K) é verdade , sendo K £ N, deve começar a provar P(1) se é verdade. Induzindo para cada i > 1 , P(i) como verdadeiro, e por hipótese de indução P(i+1) como verdadeiro.
Exemplo: Prova formal por indução da seguinte equivalência:1³ + 2³ +...+ n³ = (1 + 2 +...+ n)²
Na prova da igualdade acima, utilizaremos um lema, que diz que a soma de n números naturais vale n.(n + 1)/2, ou seja: 1 + 2 + ... + n = n.(n + 1)/2. Provaremos esse lema também por indução. Prova formal do lema:
Base de indução: Para n = 0, temos que 0 = 0.1/2 = 0, então temos uma base verdadeira.
Hipótese de indução: Suponhamos que, para um k qualquer, valha que 1 + 2 + ... + k = k.(k + 1)/2
Passo de Indução: Para o sucessor de k, ou seja, para k + 1, desejamos provar que:
1 + 2 + ... + k + (k+1) = (k + 1).[(k + 1) + 1]/2
Partimos de que: 1 + 2 + ... + k + (k+1) = (hipótese de indução)= k.(k + 1)/2 + (k + 1) = (associatividade)= (k + 1).(k/2 + 1) = (k + 1)(k + 2)/2 = (k + 1).[(k + 1) + 1]/2
Logo, conseguimos provar o que queríamos, pois supondo que a igualdade vale para k ,prova que ela vale para k + 1, e como temos uma base, a igualdade vale para a base e para todos os seus sucessores. Então, para todos os números naturais, a igualdade é válida.
Formalizando: 1 + 2 + ... + k = k.(k + 1)/2 → 1 + 2 + ... + k + (k+1) = (k + 1).[(k + 1) + 1]/2

b) Prova por Contradição
Neste método se assume como verdade o contrario do que queremos provar e assim surge uma contradição(absurdo) por isso também é chamado de Redução ao absurdo.
Exemplo: Seja x um número inteiro. Se x é par, então y = x + 5 é impar.
Assumo como x sendo um inteiro par.