Fundamentos de Matemática · Aula 5 Fundamentos de Matemática 7. O que é um número? Não é uma...

Fundamentos de Matemática

Humberto José Bortolossi

Departamento de Matemática Aplicada

Universidade Federal Fluminense

Aula 6

21 de janeiro de 2013

Aula 5 Fundamentos de Matemática 1

Números

Aula 5 Fundamentos de Matemática 2

O que é um número?

Dicionário Aurélio:

Número.[Do lat. numeru.]S. m.1. A soma total dos elementos ou unidades de um conjunto, série, etc.2. Porção ou parcela de um grupo, conjunto, etc.3. Nome, símbolo ou representação de uma quantidade. [Cf. numeral (3).]4. Entidade abstrata que corresponde a um aspecto ou a uma caraterística

mensurável de algo (quantidade, grandeza, intensidade, etc.) e queé matematicamente definida como conjunto de todos os conjuntosequivalentes a um conjunto dado.

Aula 5 Fundamentos de Matemática 3

O que é um número?

Dicionário Aurélio:

Número.[Do lat. numeru.]S. m.1. A soma total dos elementos ou unidades de um conjunto, série, etc.2. Porção ou parcela de um grupo, conjunto, etc.3. Nome, símbolo ou representação de uma quantidade. [Cf. numeral (3).]4. Entidade abstrata que corresponde a um aspecto ou a uma caraterística

mensurável de algo (quantidade, grandeza, intensidade, etc.) e queé matematicamente definida como conjunto de todos os conjuntosequivalentes a um conjunto dado.

Aula 5 Fundamentos de Matemática 4

O que é um número?

Dicionário Aurélio:

Número.[Do lat. numeru.]S. m.1. A soma total dos elementos ou unidades de um conjunto, série, etc.2. Porção ou parcela de um grupo, conjunto, etc.3. Nome, símbolo ou representação de uma quantidade. [Cf. numeral (3).]4. Entidade abstrata que corresponde a um aspecto ou a uma caraterística

mensurável de algo (quantidade, grandeza, intensidade, etc.) e queé matematicamente definida como conjunto de todos os conjuntosequivalentes a um conjunto dado.

Aula 5 Fundamentos de Matemática 5

O que é um número?

Wikipédia:

Número é a essência e o princípio de todas as coisas (Pitágoras).

Número é a relação entre a quantidade e a unidade (Newton).

Número é um composto da unidade (Euclides).

Número nada mais é do que a proporção de uma magnitude com relação a outra consideradaarbitrariamente como unidade (Euler).

Número é uma coleção de objetos de cuja natureza fazemos abstração (Boutroux).

Número é o resultado da comparação de qualquer grandeza com a unidade (BenjaminConstant).

Número é o movimento acelerado ou retardado (Aristóteles).

Número é uma coleção de unidades (Condorcet).

Número é a expressão que determina uma quantidade de coisas da mesma espécie (Baltzer).

Número é a classe de todas as classes equivalente a uma dada classe (Bertrand Russell).

Aula 5 Fundamentos de Matemática 6

O que é um número?

Wikipédia:

Número é a essência e o princípio de todas as coisas (Pitágoras).

Número é a relação entre a quantidade e a unidade (Newton).

Número é um composto da unidade (Euclides).

Número nada mais é do que a proporção de uma magnitude com relação a outra consideradaarbitrariamente como unidade (Euler).

Número é uma coleção de objetos de cuja natureza fazemos abstração (Boutroux).

Número é o resultado da comparação de qualquer grandeza com a unidade (BenjaminConstant).

Número é o movimento acelerado ou retardado (Aristóteles).

Número é uma coleção de unidades (Condorcet).

Número é a expressão que determina uma quantidade de coisas da mesma espécie (Baltzer).

Número é a classe de todas as classes equivalente a uma dada classe (Bertrand Russell).

Aula 5 Fundamentos de Matemática 7

O que é um número?

Não é uma definição formal, mas nos revela para que servem e porqual motivo foram inventados os números:

Número é o resultado da comparação entre uma grandeza e uma unidade. Sea grandeza é discreta, essa comparação chama-se uma contagem e o resultadoé um número inteiro; se a grandeza é contínua, a comparação chama-se umamedição e o resultado é um número real.

Aula 5 Fundamentos de Matemática 8

O que é um número?

Não é uma definição formal, mas nos revela para que servem e porqual motivo foram inventados os números:

Número é o resultado da comparação entre uma grandeza e uma unidade. Sea grandeza é discreta, essa comparação chama-se uma contagem e o resultadoé um número inteiro; se a grandeza é contínua, a comparação chama-se umamedição e o resultado é um número real.

Aula 5 Fundamentos de Matemática 9

Números naturais

Aula 5 Fundamentos de Matemática 10

Números naturais

númerosnaturais

númerosordinais

númeroscardinais

(substantivo) (adjetivo)

interpretados como interpretados como

Aula 5 Fundamentos de Matemática 11

Números naturais

númerosnaturais

númerosordinais

númeroscardinais

(substantivo) (adjetivo)

interpretados como interpretados como

Aula 5 Fundamentos de Matemática 12

Números naturais

númerosnaturais

númerosordinais

númeroscardinais

(substantivo) (adjetivo)

interpretados como interpretados como

Aula 5 Fundamentos de Matemática 13

Números naturais

númerosnaturais

númerosordinais

númeroscardinais

(substantivo) (adjetivo)

interpretados como interpretados como

Aula 5 Fundamentos de Matemática 14

Números naturais como números ordinais

N é um conjunto, cujos elementos são chamados númerosnaturais. Seu uso e suas propriedades são regidos pelas seguintespropriedades:

(a) Todo número natural tem um único sucessor.(b) Números naturais diferentes têm sucessores diferentes.(c) Existe um único número natural, chamado um e representado

pelo símbolo 1, que não é sucessor de nenhum outro.(d) (Axioma da Indução) Seja X um subconjunto de números

naturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axiomas de Peano

Aula 5 Fundamentos de Matemática 15

Números naturais como números ordinais

N é um conjunto, cujos elementos são chamados númerosnaturais. Seu uso e suas propriedades são regidos pelas seguintespropriedades:

(a) Todo número natural tem um único sucessor.(b) Números naturais diferentes têm sucessores diferentes.(c) Existe um único número natural, chamado um e representado

pelo símbolo 1, que não é sucessor de nenhum outro.(d) (Axioma da Indução) Seja X um subconjunto de números

naturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axiomas de Peano

Aula 5 Fundamentos de Matemática 16

Números naturais como números ordinais

N = {1,2,3,4,5,6,7, . . .}.

2 é o sucessor de 13 é o sucessor de 24 é o sucessor de 3...

......

Deve ficar claro que o conjunto N = {1,2,3,4,5,6,7, . . .} dos númerosnaturais é uma sequência de objetos abstratos que, em princípio, sãodesprovidos de significado. Cada um desses objetos (um número natural)possui apenas um lugar determinado nesta sequência. Nenhuma outrapropriedade lhes serve de definição. Todo número tem um sucessor (único)e, com exceção de 1, tem também um único antecessor (número do qual ésucessor).

[Lima, Carvalho, Morgado, Wagner e Morgado, 2003]

Aula 5 Fundamentos de Matemática 17

Números naturais como números ordinais

N = {1,2,3,4,5,6,7, . . .}.

2 é o sucessor de 13 é o sucessor de 24 é o sucessor de 3...

......

Deve ficar claro que o conjunto N = {1,2,3,4,5,6,7, . . .} dos númerosnaturais é uma sequência de objetos abstratos que, em princípio, sãodesprovidos de significado. Cada um desses objetos (um número natural)possui apenas um lugar determinado nesta sequência. Nenhuma outrapropriedade lhes serve de definição. Todo número tem um sucessor (único)e, com exceção de 1, tem também um único antecessor (número do qual ésucessor).

[Lima, Carvalho, Morgado, Wagner e Morgado, 2003]

Aula 5 Fundamentos de Matemática 18

Números naturais como números ordinais

N = {1,2,3,4,5,6,7, . . .}.

2 é o sucessor de 13 é o sucessor de 24 é o sucessor de 3...

......

Deve ficar claro que o conjunto N = {1,2,3,4,5,6,7, . . .} dos númerosnaturais é uma sequência de objetos abstratos que, em princípio, sãodesprovidos de significado. Cada um desses objetos (um número natural)possui apenas um lugar determinado nesta sequência. Nenhuma outrapropriedade lhes serve de definição. Todo número tem um sucessor (único)e, com exceção de 1, tem também um único antecessor (número do qual ésucessor).

[Lima, Carvalho, Morgado, Wagner e Morgado, 2003]

Aula 5 Fundamentos de Matemática 19

Números naturais como números ordinais: símbolos

Sucessor de n é {n}

0 ∅

1 {∅} {0}

2 {{∅}} {1}

3 {{{∅}}} {2}...

......

n {n − 1}

Aula 5 Fundamentos de Matemática 20

Números naturais como números ordinais: símbolos

Sucessor de n é {n}

0 ∅

1 {∅} {0}

2 {{∅}} {1}

3 {{{∅}}} {2}...

......

n {n − 1}

Aula 5 Fundamentos de Matemática 21

Números naturais como números ordinais: símbolos

Sucessor de n é {n}

0 ∅

1 {∅} {0}

2 {{∅}} {1}

3 {{{∅}}} {2}...

......

n {n − 1}

Aula 5 Fundamentos de Matemática 22

Números naturais como números ordinais: símbolos

Sucessor de n é {n}

0 ∅

1 {∅} {0}

2 {{∅}} {1}

3 {{{∅}}} {2}...

......

n {n − 1}

Aula 5 Fundamentos de Matemática 23

Números naturais como números ordinais: símbolos

Sucessor de n é {n}

0 ∅

1 {∅} {0}

2 {{∅}} {1}

3 {{{∅}}} {2}...

......

n {n − 1}

Aula 5 Fundamentos de Matemática 24

Números naturais como números ordinais: símbolos

Sucessor de n é {n}

0 ∅

1 {∅} {0}

2 {{∅}} {1}

3 {{{∅}}} {2}...

......

n {n − 1}

Aula 5 Fundamentos de Matemática 25

Números naturais como números ordinais: símbolos

Sucessor de n é {n}

0 ∅

1 {∅} {0}

2 {{∅}} {1}

3 {{{∅}}} {2}...

......

n {n − 1}

Aula 5 Fundamentos de Matemática 26

Números naturais como números ordinais: símbolos

Sucessor de n é {n}

0 ∅

1 {∅} {0}

2 {{∅}} {1}

3 {{{∅}}} {2}...

......

n {n − 1}

Aula 5 Fundamentos de Matemática 27

Números naturais como números ordinais: símbolos

Sucessor de n é n ∪ {n}

0 ∅

1 {∅} 0 ∪ {0}

2 {∅, {∅}} 1 ∪ {1}

3 {∅, {∅}, {∅, {∅}}} 2 ∪ {2}...

......

n (n − 1) ∪ {n − 1}

Aula 5 Fundamentos de Matemática 28

Números naturais como números ordinais: símbolos

Sucessor de n é n ∪ {n}

0 ∅

1 {∅} 0 ∪ {0}

2 {∅, {∅}} 1 ∪ {1}

3 {∅, {∅}, {∅, {∅}}} 2 ∪ {2}...

......

n (n − 1) ∪ {n − 1}

Aula 5 Fundamentos de Matemática 29

Números naturais como números ordinais: símbolos

Sucessor de n é n ∪ {n}

0 ∅

1 {∅} 0 ∪ {0}

2 {∅, {∅}} 1 ∪ {1}

3 {∅, {∅}, {∅, {∅}}} 2 ∪ {2}...

......

n (n − 1) ∪ {n − 1}

Aula 5 Fundamentos de Matemática 30

Números naturais como números ordinais: símbolos

Sucessor de n é n ∪ {n}

0 ∅

1 {∅} 0 ∪ {0}

2 {∅, {∅}} 1 ∪ {1}

3 {∅, {∅}, {∅, {∅}}} 2 ∪ {2}...

......

n (n − 1) ∪ {n − 1}

Aula 5 Fundamentos de Matemática 31

Números naturais como números ordinais: símbolos

Sucessor de n é n ∪ {n}

0 ∅

1 {∅} 0 ∪ {0}

2 {∅, {∅}} 1 ∪ {1}

3 {∅, {∅}, {∅, {∅}}} 2 ∪ {2}...

......

n (n − 1) ∪ {n − 1}

Aula 5 Fundamentos de Matemática 32

Números naturais como números ordinais: símbolos

Sucessor de n é n ∪ {n}

0 ∅

1 {∅} 0 ∪ {0}

2 {∅, {∅}} 1 ∪ {1}

3 {∅, {∅}, {∅, {∅}}} 2 ∪ {2}...

......

n (n − 1) ∪ {n − 1}

Aula 5 Fundamentos de Matemática 33

Números naturais como números ordinais: símbolos

Sucessor de n é n ∪ {n}

0 ∅

1 {∅} 0 ∪ {0}

2 {∅, {∅}} 1 ∪ {1}

3 {∅, {∅}, {∅, {∅}}} 2 ∪ {2}...

......

n (n − 1) ∪ {n − 1}

Aula 5 Fundamentos de Matemática 34

Números naturais como números ordinais: símbolos

Sucessor de n é n ∪ {n}

0 ∅

1 {∅} 0 ∪ {0}

2 {∅, {∅}} 1 ∪ {1}

3 {∅, {∅}, {∅, {∅}}} 2 ∪ {2}...

......

n (n − 1) ∪ {n − 1}

Aula 5 Fundamentos de Matemática 35

Números naturais como números ordinais: símbolos

Escrita Cuneiforme Babilônica

Aula 5 Fundamentos de Matemática 36

Números naturais como números ordinais: símbolos

Escrita Maia

Aula 5 Fundamentos de Matemática 37

Números naturais como números ordinais: símbolos

Escrita Chinesa

Aula 5 Fundamentos de Matemática 38

Números naturais como números ordinais: símbolos

Escrita Romana

1 2 3 4 5 10 50 100 500 1000I II III IV V X L C D M

Aula 5 Fundamentos de Matemática 39

Números naturais como números ordinais: símbolos

Escrita Egípcia

Aula 5 Fundamentos de Matemática 40

Números naturais como números ordinais: símbolos

Escrita Egípcia

Aula 5 Fundamentos de Matemática 41

Números naturais como números ordinais: símbolos

Escrita Braille

Aula 5 Fundamentos de Matemática 42

Números naturais como números cardinais

Apresentaremos os números naturais como números cardinaisposteriormente!

Aula 5 Fundamentos de Matemática 43

O Princípio da Indução Finita

Aula 5 Fundamentos de Matemática 44

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 45

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 46

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 47

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 48

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 49

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 50

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 51

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 52

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 53

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 54

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 55

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 56

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 57

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 58

O Principio da Indução Finita

(d) (Axioma da Indução) Seja X um subconjunto de númerosnaturais. Se 1 ∈ X e se, além disso, o sucessor de todo elementode X ainda pertence a X , então X = N.

Axioma da Indução de Peano

Considere uma sentença da forma “∀n ∈ N,P(n)” (estamos escrevendo P(n)ao invés de P para enfatizar o fato de que o predicado P depende de n). Seja

X = {n ∈ N | n satisfaz o predicado P}.

Se mostramos que(1) (Passo básico) 1 ∈ X (isto é, que 1 satisfaz o predicado P ou, ainda,

que P(1) é verdadeira),(2) (Passo indutivo) k ∈ X ⇒ k + 1 ∈ X (isto é, que se k satisfaz

o predicado P, então k + 1 também satisfaz o predicado p ou, ainda,que se P(k) é verdadeira, então P(k + 1) é verdadeira),

então, pelo Axioma de Indução de Peano, X = N, isto é, todo númeronatural n ∈ N satisfaz o predicado P e, assim, a sentença “∀n ∈ N,P(n)”é verdadeira!

Aula 5 Fundamentos de Matemática 59

O Principio da Indução Finita

Moral:

O Princípio da Indução Finita é uma técnica para tentardemonstrar que sentenças do tipo “∀n ∈ N,P(n)” sãoverdadeiras!

Aula 5 Fundamentos de Matemática 60

Protocolo de uma prova por indução

Uma demonstração por indução segue o seguinte esquema:

(1) Diga que a demonstração é por indução. Assim, o leitor já saberá qual seráa estrutura da demonstração.

(2) Especifique o predicado P(n) que se quer demonstrar que é verdadeiro para todon ∈ N (isto é, que é satisfeito para todo n ∈ N).

(3) Passo básico: mostre que P(1) é verdadeira (isto é, que n = 1 satisfazo predicado P).

(4) Passo indutivo: mostre que se P(k) é verdadeira (isto é, se k satisfazo predicado P), então P(k + 1) também é verdadeira (isto é, k + 1 também satisfazo predicado P).

Aula 5 Fundamentos de Matemática 61

Protocolo de uma prova por indução

Uma demonstração por indução segue o seguinte esquema:

(1) Diga que a demonstração é por indução. Assim, o leitor já saberá qual seráa estrutura da demonstração.

(2) Especifique o predicado P(n) que se quer demonstrar que é verdadeiro para todon ∈ N (isto é, que é satisfeito para todo n ∈ N).

(3) Passo básico: mostre que P(1) é verdadeira (isto é, que n = 1 satisfazo predicado P).

(4) Passo indutivo: mostre que se P(k) é verdadeira (isto é, se k satisfazo predicado P), então P(k + 1) também é verdadeira (isto é, k + 1 também satisfazo predicado P).

Aula 5 Fundamentos de Matemática 62

Protocolo de uma prova por indução

Uma demonstração por indução segue o seguinte esquema:

(1) Diga que a demonstração é por indução. Assim, o leitor já saberá qual seráa estrutura da demonstração.

(2) Especifique o predicado P(n) que se quer demonstrar que é verdadeiro para todon ∈ N (isto é, que é satisfeito para todo n ∈ N).

(3) Passo básico: mostre que P(1) é verdadeira (isto é, que n = 1 satisfazo predicado P).

(4) Passo indutivo: mostre que se P(k) é verdadeira (isto é, se k satisfazo predicado P), então P(k + 1) também é verdadeira (isto é, k + 1 também satisfazo predicado P).

Aula 5 Fundamentos de Matemática 63

Protocolo de uma prova por indução

Uma demonstração por indução segue o seguinte esquema:

(1) Diga que a demonstração é por indução. Assim, o leitor já saberá qual seráa estrutura da demonstração.

(2) Especifique o predicado P(n) que se quer demonstrar que é verdadeiro para todon ∈ N (isto é, que é satisfeito para todo n ∈ N).

(3) Passo básico: mostre que P(1) é verdadeira (isto é, que n = 1 satisfazo predicado P).

(4) Passo indutivo: mostre que se P(k) é verdadeira (isto é, se k satisfazo predicado P), então P(k + 1) também é verdadeira (isto é, k + 1 também satisfazo predicado P).

Aula 5 Fundamentos de Matemática 64

Protocolo de uma prova por indução

Uma demonstração por indução segue o seguinte esquema:

(1) Diga que a demonstração é por indução. Assim, o leitor já saberá qual seráa estrutura da demonstração.

(2) Especifique o predicado P(n) que se quer demonstrar que é verdadeiro para todon ∈ N (isto é, que é satisfeito para todo n ∈ N).

(3) Passo básico: mostre que P(1) é verdadeira (isto é, que n = 1 satisfazo predicado P).

(4) Passo indutivo: mostre que se P(k) é verdadeira (isto é, se k satisfazo predicado P), então P(k + 1) também é verdadeira (isto é, k + 1 também satisfazo predicado P).

Aula 5 Fundamentos de Matemática 65

Protocolo de uma prova por indução

Uma demonstração por indução segue o seguinte esquema:

(1) Diga que a demonstração é por indução. Assim, o leitor já saberá qual seráa estrutura da demonstração.

(2) Especifique o predicado P(n) que se quer demonstrar que é verdadeiro para todon ∈ N (isto é, que é satisfeito para todo n ∈ N).

(3) Passo básico: mostre que P(1) é verdadeira (isto é, que n = 1 satisfazo predicado P).

(4) Passo indutivo: mostre que se P(k) é verdadeira (isto é, se k satisfazo predicado P), então P(k + 1) também é verdadeira (isto é, k + 1 também satisfazo predicado P).

Aula 5 Fundamentos de Matemática 66

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 67

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 68

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 69

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 70

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 71

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 72

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 73

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 74

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 75

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 76

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 77

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 78

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 79

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 80

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 81

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 82

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 83

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 84

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 85

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 86

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 87

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 88

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 89

Exemplo

Mostre que ∀n ∈ N, 1 + 2 + · · ·+ n =n (n + 1)

2.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 1 + 2 + · · ·+ n = n (n + 1)/2.

(Passo básico ) Devemos mostrar que P(1) é verdadeira, isto é, que 1 satisfaz o predicado P. Em nosso caso,isso significa mostrar que 1 = (1)(1 + 1)/2. Mas (1)(1 + 1)/2 = 2/2 = 1.

(Passo indutivo) Suponha que P(k) seja verdadeira (isto é, que k satisfaz o predicado P). Devemos mostrar queP(k + 1) também é verdadeira (isto é, que k + 1 também satisfaz o predicado P). Agora, se P(k) é verdadeira,então

1 + 2 + · · ·+ k =k(k + 1)

2. (hipótese de indução)

Para mostrar que P(k + 1) é verdadeira, devemos mostrar que 1 + 2 + · · ·+ k + (k + 1) =(k + 1)((k + 1) + 1)

2.

Mas,

1 + 2 + · · ·+ k + (k + 1) (∗)=

k (k + 1)2

+ (k + 1) =k (k + 1) + 2 (k + 1)

2=

(k + 1)(k + 2)2

=(k + 1)((k + 1) + 1)

2,

onde, em (∗), usamos a hipótese de indução.

Aula 5 Fundamentos de Matemática 90

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 91

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 92

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 93

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 94

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 95

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 96

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 97

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 98

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 99

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 100

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 101

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 102

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 103

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 104

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 105

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 106

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 107

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 108

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 109

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 110

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 111

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 112

Exemplo

Mostre que ∀n ∈ N, 3 é divisor de n3 − n.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : 3 é divisor de n3 − n.

(Passo básico ) Devemos mostrar que P(1) é verdadeira. Em nosso caso, isso significa mostrar que 3 édivisor de (1)3 − 1. Mas (1)3 − 1 = 0 e 3 é divisor de 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então 3 é divisor de k3−k . Para mostrar que P(k+1) é verdadeira, devemosmostrar que 3 é divisor de (k + 1)3 − (k + 1). Agora:

(k + 1)3 − (k + 1) = k3 + 3 k2 + 3 k + 1− (k + 1) = k3 − k + 3 k2 + 3 k .

Pela hipótese de indução, 3 é divisor de k3 − k . Como 3 também é divisor de 3 k2 + 3 k , segue-se que 3é divisor de k3 − k + 3 k2 + 3 k = (k + 1)3 − (k + 1).

Aula 5 Fundamentos de Matemática 113

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 114

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 115

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 116

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 117

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 118

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 119

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 120

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 121

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 122

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 123

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 124

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 125

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 126

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 127

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 128

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 129

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 130

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 131

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 132

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 133

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 134

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 135

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 136

Onde está o erro?

Todos os cavalos têm uma mesma cor.

“Demonstração”. A prova será feita por indução. Considere o predicado

P(n) : em todo conjunto com n cavalos, todos os cavalos têm uma mesma cor.

(Passo básico ) Se n = 1, então todo cavalo em um conjunto com um único cavalo tem uma mesma cor.Logo, P(1) é verdadeira.

(Passo indutivo) Suponha que P(k) seja verdadeira, isto é, suponha que em todo conjunto com kcavalos, todos os cavalos têm uma mesma cor (hipótese de indução). Devemos mostrar que P(k + 1)é verdadeira, isto é, devemos mostrar que em todo conjunto com k + 1 cavalos, todos os cavalos têmuma mesma cor. Considere então um conjunto com k + 1 cavalos: {c1, c2, . . . , ck , ck+1}. Pela hipótesede indução, os k primeiros cavalos têm uma mesma cor: {c1, c2, . . . , ck}. Também pela hipótese deindução, os k últimos cavalos também possuem uma mesma cor: {c2, . . . , ck , ck+1}. Logo todos oscavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cor.

O erro está no passo indutivo: para concluir que todos os cavalos em {c1, c2, . . . , ck , ck+1} têm uma mesma cora partir do fato de que todos os cavalos em A = {c1, c2, . . . , ck} e B = {c2, . . . , ck , ck+1} possuírem uma mesmacor, usou-se que existe pelo menos um cavalo em comum aos dois conjuntos A e B. Mas, se k = 2, então A = {c1},B = {c2} e A ∩ B = ∅.

Aula 5 Fundamentos de Matemática 137

Ainda SobreO Princípio da Indução Finita

Aula 5 Fundamentos de Matemática 138

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 139

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 140

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 141

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 142

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 143

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 144

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 145

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 146

Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.

Aula 5 Fundamentos de Matemática 147

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 148

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 149

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 150

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 151

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 152

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 153

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 154

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 155

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 156

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 157

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 158

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 159

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 160

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 161

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 162

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 163

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 164

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 165

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 166

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 167

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 168

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 169

Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.

Aula 5 Fundamentos de Matemática 170

Seção de Exercícios

Aula 5 Fundamentos de Matemática 171