[MCTB019-17] §3 — O Princípio de Indução e demonstrações por indução

3.1. Princípio da Boa Ordem (PBO)

Definição 16 O natural ${m}$ é menor elemento de um conjunto ${A \subset {\mathbb N}}$ não vazio se, e só se,

$\displaystyle \begin{array}{rcl} &(1)&m\in A \text{ e }\\ &(2)&\forall x\in A,~a\leq x. \end{array}$

Vamos assumir o seguinte princípio como um axioma.

Princípio da Boa Ordem: Todo ${A \subset {\mathbb N}}$ não-vazio tem um menor elemento.

Esse fenômeno não ocorre nos conjuntos numéricos como ${{\mathbb Q}}$ e ${{\mathbb R}}$ . Por exemplo o intervalo ${(0,1]}$ em ${{\mathbb R}}$ não tem menor elemento, enquanto que ${[0,1]}$ em ${{\mathbb R}}$ tem menor elemento. Essa é uma das propriedades que caracterizam os números naturais, todo subconjunto não-vazio tem menor elemento.

Esse princípio pode ser usado em demonstrações, usualmente provas por contradição: supomos que um ${A}$ formado por contra-exemplos do que se quer provar é não vazio e derivamos uma contradição, concluindo que ${A}$ é vazio.

Teorema 20 Qualquer postagem que custe pelo menos oito reais pode ser feita com selos de ${3}$ e ${5}$ reais.

Demonstração: Vamos chamar ${n\in {\mathbb N}}$ de postal se ${n+8}$ pode ser um valor obtido a partir de selos de ${3}$ e ${5}$ reais. Por exemplo ${0}$ é postal pois ${8=3+5}$ , também ${1}$ é postal pois ${9 = 3\cdot 3 + 0\cdot 5}$ e ${2}$ é postal pois ${10= 0\cdot 3+ 2\cdot 5}$ .

O teorema afirma que para todo ${n\in {\mathbb N}}$ , $n$ é postal. Suponha que a afirmação do teorema é falsa. Seja ${A\subseteq {\mathbb N}}$ o subconjunto dos naturais não-postais. Por hipótese ${A\neq \emptyset}$ , portanto tem um menor elemento ${m}$ . Pelas considerações acima sabemos que ${m\geq 3}$ . Se ${m\geq 3}$ então ${m-3 \in {\mathbb N}}$ e é postal, existem naturais ${x}$ e ${y}$ tais que ${m-3=x\cdot 3 + y\cdot 5}$ .

Se ${m-3=x\cdot 3 + y\cdot 5}$ então ${m=(x+1)\cdot 3 + y\cdot 5}$ , uma contradição. $\Box$

Exercício 12 Prove usando o PBO. Para todo inteiro ${n \geq 5}$ , existem naturais ${a}$ e ${b}$ tais que ${n= 2a + 5b}$ .

(Solução)

Teorema 21 Não existe um número natural entre ${0}$ e ${1}$ .

Demonstração: Suponha que a afirmação do teorema é falsa e seja ${A}$ o conjunto dos naturais entre ${0}$ e ${1}$ . Por hipótese ${A \neq\emptyset}$ logo tem um menor elemento ${m}$ , ${0<m<1}$ .

Se ${m<1}$ então ${m^2 < m}$ , uma contradição ao fato de ${m}$ ser mínimo pois ${m^2\in {\mathbb N}}$ . Portanto, ${A=\emptyset}$ . $\Box$

Teorema 22 Todo número natural tem um divisor primo.

Demonstração: A prova dessa afirmação é por contradição, suponha que não é todo natural que admite um divisor primo e seja ${A}$ o subconjunto desses naturais. Por hipótese ${A\neq \emptyset}$ , portanto tem um menor elemento ${m}$ .

Se ${m\in A}$ então ${m}$ não é primo, logo ${m=a\cdot b}$ com ${1 < a,b < m}$ . Todo divisor primo de ${a}$ (e de ${b}$ ) divide ${m}$ , portanto ${a\in A}$ , uma contradição ( ${a}$ é menor que o menor elemento de ${A}$ ). $\Box$

Exercício 13 ${A\subseteq {\mathbb N}}$ é dito limitado superiormente se existir um natural ${n}$ tal que

$\displaystyle \forall x\in A,~ x\leq n$

e se ${n}$ com a propriedade acima pertence a ${A}$ ele é dito maior elemento de ${A}$ . Mostre que se ${A}$ é limitado superiormente e não vazio então admite maior elemento.

3.2. Princípios de indução

Há várias formulações equivalentes para o Princípio de Indução.

Teorema 23 (Princípio da Indução finita (PIF)) Seja ${X\subseteq{\mathbb N}}$ . Se

${0\in X}$ e

para todo ${k\in {\mathbb N}}$ , ${k\in X \rightarrow k+1\in X}$ ,

então ${X={\mathbb N}}$ .

Demonstração: Seja ${X}$ um subconjunto dos naturais que satisfaz as hipóteses do teorema. Suponha que a conclusão do teorema seja falsa, ou seja, suponha que ${X\subsetneqq {\mathbb N}}$ . Então ${A={\mathbb N} \setminus X}$ é não vazio e, pelo PBO, tomamos ${m}$ o menor elemento de ${A}$ .

De ${0\in X}$ temos ${m \geq 1}$ , portanto ${m-1}$ é natural. Pela minimalidade de ${m}$ temos que ${m-1\in X}$ . Pela hipótese 2 do teorema, se ${m-1\in X}$ então ${m \in X}$ . Portanto ${m\in X}$ , uma contradição. $\Box$

A forma mais comum desse princípio é enunciada como a seguir.

Corolário 24 (Princípio da Indução finita (PIF)) Seja ${P(n)}$ um predicado de números naturais. Se valem

${P(0)}$ e

para todo ${k\geq 0}$ , ${P(k)}$ implica ${P(k+1)}$ ,

então ${P(n)}$ para todo natural ${n}$ .

Demonstração: Seja ${P}$ um predicado com as hipóteses dadas. Faça ${X= \{k\in {\mathbb N} : P(k)\}}$ e temos, da hipótese 1, ${0\in X}$ e da hipótese 2, se ${k\in X}$ então ${k+1\in X}$ . Assim, estamos nas hipóteses do teorema 23 e podemos concluir que ${X={\mathbb N}}$ , ou seja, ${P(n)}$ é verdadeiro para todo natural ${n}$ . $\Box$

Corolário 25 (Princípio da Indução finita generalizado (PIF)) Sejam ${P(n)}$ um predicado de números naturais e ${a\in{\mathbb N}}$ . Se valem

${P(a)}$ e

para todo ${k\geq a}$ , ${P(k)}$ implica ${P(k+1)}$ ,

então ${P(n)}$ para todo natural ${n\geq a}$ .

Demonstração: Como na demonstração anterior, agora faça ${X= \{k\in {\mathbb N} : P(k+a)\}}$ e temos pelo teorema 23 que ${X={\mathbb N}}$ . Se ${P(n+a)}$ é verdadeiro para todo ${n\geq 0}$ então ${P(n)}$ é verdadeiro para todo ${n\geq a}$ . $\Box$

Teorema 26 (Princípio da Indução finita completo (PIFc)) Seja ${X\subseteq{\mathbb N}}$ tal que

${0\in X}$

para todo ${k\in {\mathbb N}}$ , ${\{0,1,\dots,k\}\subset X \rightarrow k+1\in X}$ .

Então ${X={\mathbb N}}$ .

Demonstração: Seja ${X\subseteq {\mathbb N}}$ que satisfaz as hipóteses do teorema.

Defina o conjunto ${Y= \{ n\in{\mathbb N} : \{0,1,\dots,n\} \subseteq X\}}$ .

Então ${0\in Y}$ pela condição 1 da hipótese do teorema.

Considere um natural arbitrário $k$ e suponha que $k\in Y$ . Se $k\in Y$ então $k+1\in Y$ pela condição 2 da hipótese do teorema. Portanto, para todo ${k\in{\mathbb N}}$ , $k\in Y \to k+1\in Y$ .

Pelo PIF, ${Y={\mathbb N}}$ portanto ${X={\mathbb N}}$ . $\Box$

Corolário 27 (Princípio da Indução finita completo (PIFc)) Seja ${P(n)}$ um predicado de números naturais. Se

${P(0)}$ e

para todo $k\geq 0$ , $P(0)$ e $P(1)$ e $\dots$ e $P(k)$ implica $P(k+1)$ ,

então ${P(n)}$ é verdadeiro para todo natural ${n\geq 0}$ .

Demonstração: Exercício. $\Box$

Corolário 28 (Princípio da Indução finita completo generalizado (PIFcg)) Sejam ${P(n)}$ um predicado de números naturais e ${a\in{\mathbb N}}$ . Se

${P(a)}$ e

para todo ${k\geq a}$ , $P(a)$ e $P(1)$ e $\dots$ e $P(k)$ implica $P(k+1)$ ,

então ${P(n)}$ para todo natural ${n\geq a}$ .

Demonstração: Exercício. $\Box$

Exercicio 14A (Outro princípio de indução) Verifique o seguinte Princípio de Indução Finita: Seja ${P(n)}$ um predicado a respeito de ${n\in{\mathbb N}}$ . Se

${P(0)}$ e ${P(1)}$ e … e ${P(k)}$ e

para todo ${n\in{\mathbb N}}$ , Se ${(P(n)}$ e ${P(n+1)}$ e … e ${P(n+k-1))}$ então ${P(n+k)}$

então ${P(n)}$ para todo ${n\in{\mathbb N}}$ .

Exercício 14B (Outro princípio de Indução) Seja ${a_i}$ uma sequência (estritamente) crescente de números naturais. Verifique o seguinte Princípio de Indução Finita: Seja ${P(n)}$ um predicado a respeito de ${n\in{\mathbb N}}$ . Se

${P(a_i)}$ para todo ${i\in {\mathbb N}}$ e

${P(j)}$ implica ${P(j-1)}$ para todo ${j> a_1}$

então ${P(n)}$ para todo ${n\geq a_1}$ .

3.3. Equivalência

Acima deduzimos PIFc de PIF e PIF de PBO. Todos esses princípios são, de fato, equivalentes, logo se assumimos qualquer um deles o outro pode ser provado. Para provar a equivalência vamos provar que PBO segue de PIFc e teremos

$\displaystyle \mathrm{PBO}\Rightarrow \mathrm{PIF} \Rightarrow \mathrm{PIFc} \Rightarrow \mathrm{PBO}$

Demonstração: [Demonstração de PIFc ${\Rightarrow}$ PBO]
Seja ${A\subset {\mathbb N}}$ não vazio. Vamos provar que ${A}$ tem um menor elemento. A prova é por contradição, suponha que ${A}$ não tem menor elemento. Definimos

$\displaystyle X:=\{n\in{\mathbb N} : n \not\in A\}$

e vamos provar
que: ${(i)}$ ${0\in X}$ , e ${(ii)}$ para todo ${k\in{\mathbb N}}$ , se ${\{0,\dots,k\} \subset X}$ então ${k+1\in X}$ .

Se ${0\not\in X}$ então ${0\in A}$ , portanto ${0}$ é o menor elemento de ${A}$ , contradição. Com isso provamos que ${0\in X}$ . Seja ${k\geq 0}$ arbitrário e suponha ${\{0,\dots,k\} \subset X}$ . Se ${k+1\not\in X}$ então ${k+1\in A}$ , portanto ${k+1}$ é o menor elemento de ${A}$ , já que ${\{0,\dots,k\} \subset X}$ , contradição. Portanto ${k+1\in X}$ e, generalizando universalmente, provamos para todo ${k\in{\mathbb N}}$ , se ${\{0,\dots,k\} \subset X}$ então ${k+1\in X}$ .

Com ${(i)}$ e ${(ii)}$ podemos usar o PIFc para concluir que ${X={\mathbb N}}$ , ou seja ${A=\emptyset}$ , uma contradição. Portanto, $A$ tem menor elemento. $\Box$

3.4. Demonstrações por indução

Indução matemática também é uma técnica de prova para proposições da forma ${\mathrm{para~todo~} n\geq a,~P(n)}$ . Numa prova por indução provamos ${P(a)}$ (isto é, verificamos que a instanciação da variável com ${a}$ resulta numa sentença verdadeira) que é dito a base da indução e provamos ${\forall n\geq a\big(P(n) \rightarrow P(n+1)\big)}$ (usando as estratégias que já aprendemos para isso) que é dito o passo da indução.

Exemplo: Para todo ${n\in{\mathbb N}}$ , ${0+1+\cdots+n = n(n+1)/2}$ .

base: Para $n=0$ a igualdade afirmada se verifica ${0 = 0(0+1)/2}$

passo: Seja ${k\geq 0}$ um natural arbitrário e suponha que ${0+1+\cdots+k = k(k+1)/2}$ . Precisamos mostrar que ${0+1+\cdots+k +( k+1 ) = (k+1)(k+2)/2}$ .

Exemplo: Para todo ${n \geq 5}$ , ${2^n > n^2}$ .

base: Para $n=5$ a desigualdade afirmada se verifica ${2^5 > 5^2}$ .

passo: Seja ${k\geq 5}$ um natural arbitrário e suponha que ${2^k > k^2}$ . Precisamos mostrar que ${2^{k+1} > (k+1)^2}$ .

A base é importante, sem ela poderíamos pensar que sabemos provar

${n(n+1)}$ é ímpar para todo ${n\geq1}$

que obviamente não vale, pois conseguimos provar a implicação do passo da indução para essa sentença. Vamos provar que

para todo ${n\geq1}$ , ${n(n+1)}$ ímpar ${\rightarrow (n+1)(n+2)}$ ímpar.

Seja ${t>1}$ um natural e suponha que ${t(t+1)}$ é ímpar. Então

$\displaystyle \begin{array}{rcl} (t+1)(t+2) = (t+1)t + (t+1)2 \end{array}$

que é da forma “ímpar ${+}$ par”, portanto ímpar.

O passo é importante, uma prova descuidada do passo indutivo pode por tudo a perder. Por exemplo, vamos provar que todos os naturais são iguais. Tomemos ${\max \{a,b\}}$ como o maior dentre os naturais ${a}$ e ${b}$ , por exemplo, ${\max \{1,2\}=\max\{2,1\}=2}$ e ${\max\{3,3\}=3}$ .

Seja ${P(n)}$ a sentença

$\displaystyle \forall a\in{\mathbb N}\,\forall b\in{\mathbb N}\, (\max\{a,b\}=n \rightarrow a=b).$

Se ${\max\{a,b\}=0}$ então ${a=b=0}$ , portanto ${P(0)}$ é verdadeiro.

Seja ${t\in{\mathbb N}}$ arbitrário e assuma ${P(t)}$ , isto é, que

$\displaystyle \forall a\,\forall b\, (\max\{a,b\}=t \rightarrow a=b).$

Vamos provar ${P(t+1)}$ , isto é, que ${\forall a\,\forall b\,(\max\{a,b\}=t+1 \rightarrow a=b)}$ .

Sejam ${a}$ e ${b}$ naturais arbitrário tais que ${\max\{a,b\}=t+1}$ .

Se fizermos ${x=a-1}$ e ${y=b-1}$ , então ${\max\{x,y\}=t}$ e, pela hipótese da indução, deduzimos que ${x=y}$ . Mas, se ${x=y}$ então ${a=b}$ . Portanto ${a=b}$ , e com isso temos ${P(t+1)}$ .

Pelo PIF, ${P(n)}$ é verdadeiro para todo ${n\in{\mathbb N}}$ .

Para concluir, sejam ${a}$ e ${b}$ números naturais. Se ${\max\{a,b\}=a}$ então ${a=b}$ por ${P(a)}$ . Se ${\max\{a,b\}=b}$ então ${a=b}$ por ${P(b)}$ . Logo quaisquer dois números naturais são iguais.

Qual é o problema da demonstração? (Solução)

Exemplo: Todo polígono convexo com ${n \geq 3}$ lados pode ser decomposto em ${n-2}$ triângulos.

Exemplo: Se em ${2^n}$ moedas 1 é falsa, mais leve, então é possível descobrir a moeda falsa em ${n}$ pesagens numa balança de 2 pratos.

Demonstração: Se ${n=0}$ então a afirmação vale trivialmente, a única moeda é a falsa.

Seja ${k\geq 0}$ um natural arbitrário e suponha que para ${2^k}$ moedas sabemos encontrar a mais leve usando ${k}$ pesagens. Consideremos um conjunto com ${2^{k+1}}$ moedas e dividimos as moedas em duas partes iguais de ${2^k}$ moedas. Comparamos essas metades usando 1 pesagem e na metade mais leve achamos a moeda falsa com ${k}$ pesagens, totalizando ${k+1}$ pesagens.

Portanto, pelo PIF, se em ${2^n}$ moedas 1 é mais leve, então é possível descobrir a moeda leve em ${n}$ pesagens, para qualquer ${n\geq 0}$ . $\Box$

Exemplo: Para todo natural ${n \geq 2}$ , ${n}$ é primo ou pode ser escrito como produto de primos.

Numa tentativa de prova usando o corolário 24 temos:

—a base é fácil, ${n=2}$ é primo;
—no passo temos que provar que se ${n}$ é primo ou produto de primos então ${n+1}$ é primo ou produto de primos. Se ${n+1}$ é primo a implicação é verdadeira (vacuidade), se ${n+1}$ é composto então, por definição de número composto ${n+1 = ab}$ onde ${1 \leq a , b \leq n}$ são números naturais. Se soubéssemos que ${a}$ e ${b}$ são primos ou produtos de primos então ${n+1}$ seria produto de primos, mas só o que sabemos é que ${n}$ é produto de primos.

Esse problema pode ser contornado com o corolário 27. Se a hipótese vale para todo ${k\leq n}$ então ${a}$ é produto de primos, ${b}$ é produto de primos, portanto ${a\cdot b}$ é produto de primos:

Seja ${P(n)}$ a sentença ${n}$ é primo ou pode ser escrito como produto de primos.

base: ${2}$ é primo, portanto ${P(2)}$ .

passo: Seja ${k\geq 2}$ um natural arbitrário e suponha

$\displaystyle P(2) \land P(3) \land\cdots\land P(k) \ \ \ \ \ (25)$

Precisamos provar ${P(k+1)}$ . Em dois casos: ${(i)}$ se ${k+1}$ é primo então ${P(k+1)}$ . ${(ii)}$ se ${k+1}$ não é primo então ${k+1=ab}$ com ${2\leq a,b\leq k}$ . Pela hipótese (25) valem ${P(a)}$ e ${P(b)}$ portanto ${ab}$ é um produto de primos, portanto ${P(k+1)}$ . Pelo PIFc, ${P(n)}$ para todo ${n\geq 2}$ .

Outro exemplo de prova errada: Seja ${P(n)}$ a sentença: para todo ${n}$ natural, ${6n=0}$ .

Vamos provar ${P(n)}$ por indução em ${n}$ . Para ${n=0}$ a sentença ${P(0)}$ é, claramente, verdadeira.

Seja ${t}$ um natural arbitrário e vamos provar que ${P(0) \land P(1) \land \cdots \land P(t) \rightarrow P(t+1)}$ .

Assuma ${P(0) \land P(1) \land \cdots \land P(t)}$ . Então ${6(t+1) = 6\cdot t + 6\cdot 1}$ e, por ${P(t)}$ e ${P(1)}$ temos ${6\cdot t + 6\cdot 1 = 0+0 =0}$ .

Portanto ${6(t+1) = 0}$ , ou seja ${P(t+1)}$ .

Pelo PIFc, ${P(n)}$ vale para todo ${n}$ .

Qual o erro?

3.5. Princípio da casa dos pombos

O princípio da casa dos pombos diz que se em ${n}$ casas ( ${n\geq 1}$ ) distribuirmos mais de ${n}$ pombos, então alguma caixa conterá mais de um pombo.

Teorema 29 (PCP) Se em ${n}$ caixas ( ${n\geq 1}$ ) distribuírmos ${n+1}$ objetos, então alguma caixa conterá mais de um objeto.

Demonstração: Provaremos usando indução no número de caixas ${n}$ .

Se ${n=1}$ a afirmação é verdadeira.

Seja ${k\geq 1}$ arbitrário e suponha que se distribuímos ${k+1}$ objetos em ${k}$ caixas, então alguma caixa conterá mais de um objeto.

Considere que ${k+2}$ objetos são distribuídos em ${k+1}$ caixas. Escolhemos uma das caixas, se essa caixa escolhida tem mais de um objeto, a afirmação está provada. Senão, na caixa escolhida há no máximo um objeto. Isso significa que ${k+1}$ objetos foram distribuídos nas outras ${k}$ caixas restantes logo, por hipótese, alguma caixa restante conterá mais de um objeto. $\Box$

Exercício Sejam ${A_1,A_2,\dots,A_n}$ conjuntos e ${n\geq 2}$ . Suponha que para dois conjuntos quaisquer ${A_i}$ e ${A_j}$ vale que ${A_i\subseteq A_j}$ ou ${A_j \subseteq A_i}$ . Prove, por indução, um desses conjuntos é subconjunto de todos eles.

Exercício Deduza o PIF do PCP.

3.6. Definições recursivas

Definição 17 Quando a indução é usada para definir objetos chamamos de definição recursiva .

Conhecemos vários exemplos de definição recursiva

o fatorial: ${0!=1}$ e para todo ${n> 0}$ , ${n! = n\cdot (n-1)!}$ ;
o somatório: ${\sum_{i=0}^0 x_i= x_0}$ e para todo ${n > 0}$ , ${\sum_{i=0}^{n} x_i = x_n + \sum_{i=0}^{n-1}x_i}$ ;
o produtório: ${\prod_{i=0}^0 x_i= x_0}$ e para todo ${n > 0}$ , ${\prod_{i=0}^{n} x_i = x_n \cdot \prod_{i=0}^{n-1}x_i}$ ;
exponencial: ${a^0=1}$ e e para todo ${n>0}$ , ${a^{n} = a^{n-1}\cdot a}$ ;
sequência de Fibonacci: ${F_0 = 0}$ , ${F_1=1}$ e ${F_n=F_{n-1}+F_{n-1}}$ para todo ${n\>2}$ .

Definimos qualquer função com domínio ${{\mathbb N}}$ recursivamente em duas etapas: na base especificamos o valor da função ${0}$ e no passo damos uma regra para encontrar seu valor em um inteiro ${n}$ em função de seus valores no inteiros menores que ${n}$ . Tal definição é chamada de definição recursiva ou indutiva.

Definição 18 Uma função ${f:{\mathbb N}\rightarrow{\mathbb R}}$ é o mesmo que uma sequência ${a_0, a_1, \dots}$ com ${f(i) = a_i}$ . Uma recorrência é uma sequência definida recursivamente.

As funções definidas recursivamente estão bem definidas. Isso significa que dado qualquer ${n}$ podemos usar as duas partes da definição para encontrar o valor da função no ponto ${n}$ de forma inequívoca.

Exercício 16 Use o PIF para provar que uma função ${F}$ definida pela especificação de ${F (0)}$ e uma regra para obtenção de ${F (n + 1)}$ a partir de ${ F (n)}$ está bem definida.

Exercício 17 Use o PIFc para provar que uma função ${F}$ definida especificando ${F (0)}$ e uma regra para obter ${F (n + 1)}$ dos valores ${F (k)}$ para ${k = 0, 1, 2,\dots, n}$ está bem definida.

Exemplo: uma progressão aritmética que começa em ${a\in{\mathbb R}}$ e tem razão ${r\in{\mathbb R}}$ é uma sequência ${a_0,a_1,\dots}$ tal que

$\displaystyle \begin{array}{rcl} a_0 &=& a \\ a_{n+1} &=& a_n + r \text{ para todo }n\geq 0. \end{array}$

Podemos provar por indução que para todo ${n}$ , ${a_n=nr+a}$ . De fato, a base ( ${n=0}$ ) é verdadeira, ${a_0 = 0r+a=a}$ portanto confere com a definição. Seja ${k}$ um natural arbitrário e suponha que ${a_k = kr+a}$ . Vamos provar que ${a_{k+1}=(k+1)r+a}$ .

${a_{k+1} = a_k + r}$ por definição e ${a_k = kr+a}$ por hipótese. Portanto, ${a_{k+1} = (k+1)r+a}$ . Portanto, pelo PIF, para todo ${n}$ , ${a_n=nr+a}$ .

Exercício 18 Uma progressão geométrica é uma sequência definida pela recorrência ${x_0 = a}$ e ${ x_n = x_{n-1} \cdot r}$ para todo ${n>0}$ onde ${a}$ e ${r}$ são valores reais, chamados de termo inicial e razão da progressão. Prove usando indução que o termo geral de uma progressão geométrica é ${x_n = ar^n}$ para todo ${n\geq 0}$ .

Teorema 30 Defina ${X\subset {\mathbb N}}$ por

${1\in X}$

para todo ${a\in X}$ , ${a+2 \in X}$ .

OS únicos elementos em $X$ são os obtidos pela aplicação dessa regras. Então ${X}$ é o subconjunto dos naturais ímpares.

Para provar que ${X=\{2n+1:n\in{\mathbb N}\}}$ provaremos duas inclusões ${X\subseteq \{2n+1:n\in{\mathbb N}\}}$ e ${\{2n+1:n\in{\mathbb N}\}\subseteq X}$ .

Demonstração:

Provamos que ${X\subseteq \{2n+1:n\in\mathbb N\}}$ por contradição. Suponha existir um elemento de ${X}$ que não está em ${\{2n+1:n\in\mathbb N\}}$ . Então ${A := \{ n\in \mathbb N \colon n\in X \text{ e } n \text{ n\~ao \'e \'impar}\}\neq \emptyset}$ . Seja ${m}$ o menor deles, que existe pelo PBO. Certamente ${m>1}$ . De ${m>1}$ temos ${m-2\in \mathbb N}$ e da definição ${m-2\in X}$ . De ${m}$ mínimo, ${m-2 \in \{2n+1:n\in\mathbb N\}}$ , portanto ${m=2(k+1)+1}$ e ${m\in A}$ , uma contradição.

Para provar que ${\{2n+1:n\in\mathbb N\}\subseteq X}$ vamos usar indução. A base: para ${n=0}$ temos ${2\cdot 0+1 =1}$ e ${1 \in X}$ pela hipótese 1 do enunciado do teorema. Seja ${k\in\mathbb N}$ arbitrário e suponha que ${2k+1\in X}$ . Então ${2k+1+2 \in X}$ , pela hipótese 2 do teorema, ou seja, ${2(k+1) +1 \in X}$ . Pelo PIF temos ${2n+1\in X}$ para todo ${n}$ . $\Box$

Exercício 19 Suponha que um casal de urubus começa a dar crias com dois anos de idade, e produz ${6}$ crias (três casais) de urubuzinhos a cada ano. Suponha que um lixão começou a ser frequentado por ${1}$ casal recém-nascido e que nenhum urubu é acrescentado ou eliminado do lixão. Escreva uma definição recursiva para o número de urubus que existem no ano ${n}$ .

Exercício Considere um conjunto $S$ de números naturais definido recursivamente da seguinte maneira:

$3\in S$ ;

se $x\in S$ e $y\in S$ então $x+y\in S$ .

Prove que $S$ é o conjunto dos naturais múltiplos de 3.

Obs: $x$ , $y$ acima não são necessariamente distintos. Os únicos elementos de $S$ são os obtidos pelas regras acima.
Dica: Primeiro prove que para todo natural $n$ , vale $3n\in S$ . Depois prove que todo elemento de $S$ é múltiplo de 3.