Lista De Exercícios Resolvidos

Parte I: Técnicas de prova e definições indutivas

1) Vamos provar a conjectura “Para um número ser primo não é suficiente que seja ímpar”. Siga os seguintes passos para prová-la:

(a) Desconsidere o não do enunciado e coloque o restante na forma “se P então Q”

(b) Para provar a frase original “não (se P então Q)” basta refutar “se P então Q”

(a) Como o enunciado fala em suficiência o P será a segunda parte “o número é impar”. Logo, o enunciado sem a negação será “se um número é ímpar então ele é primo”

(b) para refutar (a) basta encontrar um contra-exemplo. Ora, 9 é ímpar mas não é primo. Logo a conjectura original está provada.

2)

Prove que para um inteiro n, n3+5 é ímpar se somente se n é par:

a) por contraposição (a parte ‘se’)

Temos que provar que Se n é par então n3+5 é ímpar por contraposição, ou seja:

. Temos que provar que Se n3+5 é par então n é ímpar

Se n3+5 é par então n3+5 = 2k logo n3 +2.2 + 1 = 2k, logo n3 tem que ser ímpar pois se fosse par daria 2m+2.2 + 1= 2(m+2) + 1 o que é ímpar.

Mas, se n3 é ímpar, n não pode ser par pois nesse caso n3=2r.2r.2r = 2(4r2) que é par.

Logo n tem que ser ímpar. c.q.d.

Temos que provar que Se n não é par então n3+5 não é ímpar.

Como, por hipótese n é ímpar, será da forma n= 2k+1 para algum k. Então

n3 +5= (2k+1)3 +5= (4k2 + 4k+1)(2k+1)+5 = 8k3+8k+2k+4k2+4k+1+5 =

8k3+4k2+14k+6= 2 (4k3+2k714k+3), logo r= 4k3+2k714k+3 é um inteiro e temos que

n3 +5= 2r, portanto é par. C.Q.D.

b) por absurdo ( a parte ‘somente se’)

Temos que provar que Se n3+5 é ímpar então n é par por absurdo.

Suponhamos que n3+5 é ímpar mas n também é ímpar.

Mas, se n é ímpar, é da forma 2k+1, nesse caso teríamos

n3 +5 = (2k+1)3 = (2k+1) (2k+1) (2k+1) + 5 = (4k2+ 4k+3)(2k+1) + 5 =

8k3 + 4k2 + 8k2 + 4k + 6k + 3 + 5 = 8k3 + 12k2 + 8k + 8 = 2(4k3 + 6k2 + 4k + 4)

Que é para, em contradição de que n3+5 é ímpar. c.q.d.

3) Prove que “se x é positivo então x+1 é positivo”

a) por contraposição

b) por contradição

(a) provar que “se x+1 não é positivo então x não é positivo”. Ora, se x+1  0, como x<x+1, teremos que x também é negativo;

(b) suponha que x  0 e x+1 < 0. Como x  0, e x+1 > x, teremos x+1 > 0, contradição com a hipótese.

4) (a) Mostre, por contradição, que a função inversa de uma função bijetiva f(x), é única.

Suponhamos que f(x) tem duas inversas f1-1(y) e f2-1(y). Como as duas funções são diferentes existe um y tal que f1-1(y)  f2-1(y). Neste caso, se x1= f1-1(y) e x2 = f2-1(y) temos que, f(x1)=y e f(x2)=y, já que as duas são inversas de f(x). Mas neste caso f(x) não é injetiva e, portanto, não é bijetiva! CONTRADIÇÃO.

(b) Prove, por indução, que para todo inteiro positivo n vale que 7n-2n é divisível por 5.

Para n=1 temos 7-2=5 OK

Supondo que 7n-2n é divisível por 5 existe um k tal que 7n-2n=5k.

Agora 7(n+1) – 2(n+1)= 7n+7-(2n+2)= 7n-2n +7-2 = 5k +7-2=5(k+1). CONFIRMADO

5) A seqüência de números triangulares é 1, 3, 6, 10, .. é baseada nos triângulos

1 3 6

Encontre a relação de recorrência e a fórmula fechada desta seqüência. Para encontrar a fórmula fechada use o princípio expandir, supor, verificar.

A sequência será 1, 3(=1+2), 6(=3+3), 10(=6+4), 15(=10+5), 21(=15+6),.., logo a

relação de recorrência será: S(1) = 1 e S(n) = S(n-1) + n.

Fórmula fechada:

Expandir: S(1) = 1; S(2) = 1 + 2; S(3) = 1 + 2 + 3; S(4) = 1 + 2 + 3 + 4

Supor: S(n) = i=1,..,n i

Verificar: S(1)=1 = i=1,..,1 i

Supondo verdadeiro que S(n) = i=1,..,n i temos que

S(n+1) = S(n) + n+1 = i=1,..,n i + n+1 = i=1,..,n+1 i C.Q.D.O

6) Mostre, por indução, que para a seqüência de Fibonacci vale a relação

F(n) < 2n

(N.B. a seqüência de Fibonacci é dada por F(1)=1; F(2)=2 e F(n)=F(n-1) + F(n-2))

Hipótese de indução: F(1) = 1 < 21, F(2) = 2 < 22, F(n-1) < 2n-1 e F(n) < 2n.

Vamos mostrar que F(n+1) = < 2n+1 para n > 2

Por definição temos que

F(n+1) = F(n) + F(n-1), substituindo a hipótese de indução, temos que

F(n+1) < = 2. 2n-1 + 2n-1. = 3.2n-1 < 4.2n-1 = 2n+1 está provada a conjectura.

Na prova acima foi usada ‘indução completa’. A prova por indução simples seria:

F(n+1) = F(n) + F(n-1), pela definição de F(n)

= F(n-1)+F(n-2) + F(n-1), pela hipótese de indução

< 2n + F(n-1) como F(n-1) = F(n) – F(n-2)

< 2n + 2n – F(n-2) = 2n+1 – F(n-2)

Então temos F(n+1) + F(n-2) < 2n+1 e, como F(n-2)