Questão 1 (Demonstração por casos)

Mostre que se x ou y forem inteiros pares, então xy é par.

• i) Temos que um número par n pode ser descrito como n = 2k, e um número ímpar t como t = 2w + 1;

• ii) Temos que: x = 2k e y = 2w + 1, então:

  

  

  

  
  
• iii) Como a multiplicação e a soma entre inteiros resulta em um outro inteiro, então a afirmação se torna verdadeira;

• iv) Da mesma forma do item i), temos que: x = 2k + 1 e y = 2w, então:

  

  

  

  
  
• v) Pela demosntração por casos, mostramos a veracidade da afirmativa.

Questão 2 (Demonstração direta)

Dê uma demonstração direta ao teorema "Se um inteiro é divisível por 6, então duas vezes esse inteiro é divisível por 4".

• i) Como n|6, temos que n = 6k, para k inteiro;

• ii) Atribuindo a condição do enunciado em ambos os lados da equação, temos:

  

  
  
• iii) Por definição, a multiplicação entre inteiros resulta em um inteiro. Ou seja, existe um inteiro que multiplicado por k resultará em um n.

Questão 3 (Demonstração por contraposição)

Prove que o número n é um inteiro ímpar se, e somente se,

para algum inteiro k.

• i) Note que se trata de uma implicação bicondicional, deve-se provar ambos os lados da implicação:

  • Se n é um inteiro ímpar. então 3n + 5 = 6k + 8 para algum inteiro k;
  • Se 3n + 5 = 6k + 8 para algum inteiro k, então n é um inteiro ímpar.

• ii) Podemos provar o primeiro caso por demosntração direta, substituindo n:

  

  

• iii) Na segunda condição, temos que:

  

  

• iv) Por contraposição, temos:

  

  

  

• v) Substituindo n, temos:

  

• vi) Portanto, por contraposição, demonstra-se a segunda condição, verificando-se o teorema.

Questão 4 (Demonstração por contradição)

Mostre por absurdo que é um número irracional.

• i) Vamos supor que seja um número racional;
• ii) Um número racional é um número que pode ser escrito na forma a/b, sendo a um inteiro e b um inteiro diferente de 0;
• iii) Suponhamos que ;
• iv) Então, a e b, não podem ser ambos pares, pois se fossem, daria para simplificar;

• v) Elevando os dois lados ao quadrado, obtemos:

  

• vi) Então,

  

• vii) Por definição, temos que a é par. Então b não pode ser par;

• viii) Como a é par, pode ser escrito na forma de a = 2k:

  

• ix) Agora, pelos mesmos motivos do item vii), temos que b também é par. O que se mostra um absurdo;
• x) Portanto, prova-se por contradição, a afirmação do enunciado.

Questão 5 (Indução Fraca)

Mostrar para todo inteiro positivo n,

• Passo 1: Para demonstrar o caso base , vamos usar n = 1, assim temos:

  

Para o caso base, a afirmação é verdadeira.

• Passo 2: Na hipótese indutiva, tomaremos a afirmação para n = k como verdadeira, ou seja:

  

• Passo 3: Deve-se mostrar, para n = k +1, que

  

é verdadeira.

i) Utilizando a conjectura fornecida no passo ii), temos que:

ii) Tornando os membros com o mesmo denominador na primeira parte da igualdade, temos que

iii) Aplicando a distributiva entre os elementos em ambas as partes, temos que:

iv) Como demonstramos a veracidade da afirmação inicial para n = k +1, concluímos o Passo 3 e provamos por indução a integridade desta mesma.

Questão 6 (Demonstração Direta)

Prove que para todo a, b, c inteiros, se a|b e a|c então a|(b+c)

• i) Temos por definição que:

  

  

• ii) Seguindo a lógica do passo i), temos que:

  

• iii) Substituindo os valores do passo i):

  

  

  

• iv) Por definição, como a soma de dois inteiros resulta em um inteiro, então prova-se por demonstração direta que se a|b e a|c então a|(b+c).

Questão 7 (Indução Forte)

Prove, usando indução forte, que é possível pagar qualquer quantia (inteira) maior que R$ 7 usando notas de R$ 3 (caso existissem) e de R$ 5.

• Passo base: Para P(8), P(9), P(10), P(11), temos que:

  

  

  

  

ou seja, para o caso base, a afirmação é verdadeira;

• Passo indutivo: P(t) é verdadeiro para 7 < t <= k.
• Por essa hipótese, podemos concluir que P(k - 2) é verdadeiro, pois k - 2 > 7;
• Ou seja, podemos formar valores de k - 2 reais utilizando apenas notas de 3 e 5 reais;
• E, para formar o valor de k + 1 reais, basta adicionar mais uma nota de 3 à quantia de k - 2 reais.

Questão 8 (Indução Fraca)

Mostre que uma árvore binária completa de k níveis possui 2^k - 1 vértices.

• Passo 1: Para demonstrar o caso base, vamos usar k = 1, assim temos:

  

Para o caso base, a afirmação é verdadeira.

• Passo 2: Na hipótese indutiva, tomaremos a afirmação para k = a como verdadeira, ou seja:

  

onde a primeira parte da igualdade representa a sequência natural de uma árvore binária completa.

• Passo 3: Deve-se mostrar que o somatório de vértices dos a + 1 níveis é igual a .

i) Temos que a soma dos vértices entre os a + 1 níveis, será dado pelo somatório fornecido pela conjectura apresentada no Passo 2 adicionado pelo próximo elemento da sequência, que será o somatório do nível a + 1.

ii) Ou seja:

iii) Manipulando a segunda e terceira parte da igualdade, temos:

iv) Sabendo, por definição que x + x = 2x, temos:

v) Como demonstramos a veracidade da afirmação inicial para k = a + 1, concluímos o passo 3, e provamos por indução a integridade desta mesma.