Indução

Um dos axiomas de Peano para os números naturais diz que para { {X\subset {\mathbb N}}}

\displaystyle \big( 0\in X \mathrm{~ e ~para~todo~} n,~(n\in X\Rightarrow n+1\in X)\big) \Longrightarrow X={\mathbb N}. \ \ \ \ \ (56)

Com isso temos o seguintes argumentos válidos: seja {P(n)} uma sentença aberta.

Teorema (Princípio da Indução Finita – 1ª versão) Se

\displaystyle P(0){~\mathrm{ e }~} \mathrm{para~todo~} n\in {\mathbb N},~\big(P(n) \Rightarrow P(n+1)\big)

então

\displaystyle \mathrm{para~todo~} n\in {\mathbb N},~P(n).

Desse resultado temos:

Teorema (Princípio da Indução Finita – 2ª versão) Seja {a\in{\mathbb N}}. Se

\displaystyle P(a){~\mathrm{ e }~} \mathrm{para~todo~} n\geq a,~\big(P(n) \Rightarrow P(n+1)\big)

então

\displaystyle \mathrm{para~todo~} n\geq a,~P(n).

Prova: Para

\displaystyle  X=\{m \in{\mathbb N} \colon P(m+a)\}.

se {P(a)} então {0\in X}. Seja {n\geq a} e defina {m=n-a}. Se {P(n) \Rightarrow P(n+1)} então {m\in X \Rightarrow m+1 \in X}. Por (56) {X={\mathbb N}}, portanto, {P(n)} para todo {n\geq a}. \Box

Indução matemática é 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)} que é dito a base da indução, e provamos {\mathrm{para~todo~} n\geq a,~\big(P(n) \Rightarrow P(n+1)\big)} que é dito o passo da indução.

Exemplo Para todo {n\in{\mathbb N}},  prova-se por indução que {\sum_{i=0}^n i = n(n+1)/2}.

Exemplo Para todo {n \geq 5}, prova-se por indução que {2^n > n^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 {n>1} um natural e suponha que {n(n+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.

A passo é importante, uma prova descuidada pode por tudo a perder. Por exemplo, seja {P(t)} a sentença

\displaystyle  \mathrm{para~todo~} a\in{\mathbb N},~\mathrm{para~todo~} b\in{\mathbb N}, (\max\{a,b\}=t \Rightarrow a=b).

Se {\max\{a,b\}=0} então {a=b=0}, portanto a base é verdadeira.

Seja {t\in{\mathbb N}}, suponha que

\displaystyle  \mathrm{para~todo~} a,~\mathrm{para~todo~} b, (\max\{a,b\}=t-1 \Rightarrow a=b)

e vamos provar que {\mathrm{para~todo~} a,} {\mathrm{para~todo~} b,} {(\max\{a,b\}=t \Rightarrow a=b)}. Se {\max\{a,b\}=t} então {\max\{a-1,b-1\}=t-1}, portanto pela hipótese acima {a-1=b-1}, logo {a=b}.

Claramente, {P(t)} é falso (determine um contraexemplo). O problema com o passo é que {P(0) \not\Rightarrow P(1)} quando {a} ou {b} vale {0}.



Teorema (Pricípio da Indução Finita – 3ª versão) Sejam {a\in{\mathbb N}} e {P(n)} uma sentença aberta. Se

\displaystyle  P(a) \quad {~\mathrm{ e }~}

\displaystyle \mathrm{para~todo~} n\geq a,~\big( \mathrm{para~todo~} k\in [a..n],~P(k) \big) \Rightarrow P(n+1)

então

\displaystyle  \mathrm{para~todo~} n\geq a,~P(n).

Ou seja, {\mathrm{para~todo~} n\geq a,~P(n)} é verdadeiro sempre que {P(a)} é verdadeiro e {\mathrm{para~todo~} n\geq a} é verdadeiro que

\displaystyle  \big(P(a){~\mathrm{ e }~} P(a+1){~\mathrm{ e }~}\cdots{~\mathrm{ e }~} P(n)\big) \Rightarrow P(n+1) .

Prova: Exercício. \Box

Exemplo. Todo natural {n \geq 2} é primo ou pode ser escrito como produto de primos.

Exemplo. Todo inteiro {n\geq 7} poder ser escrito como múltiplo de 2 mais múltiplo de 5.

Exemplo. Seja {P(n)} a sentença: {\mathrm{para~todo~} n\in{\mathbb N},~6n=0}. Vamos provar {P(n)} por indução. {P(0)} é verdadeiro. Seja {n} um natural arbitrário e vamos provar que para todo {n}, {P(0) {~\mathrm{ e }~} P(1) {~\mathrm{ e }~} \cdots {~\mathrm{ e }~} P(n) \Rightarrow P(n+1)}. Suponhamos {P(0) {~\mathrm{ e }~} P(1) {~\mathrm{ e }~} \cdots {~\mathrm{ e }~} P(n)}. Então

\displaystyle  \begin{array}{rcl}  6(n+1) = 6\cdot n + 6\cdot 1 = 0+0 =0 \end{array}

pois de {P(n)} temos {6n=0} e de {P(1)} temos {6\cdot 1 = 0}; qual é o erro ?

Exercício 1 Todos os marcianos são verdes. Vamos provar por indução sobre o número de marcianos em Marte.

  • Base. Se o número de marcianos é {1}, todos os marcianos são verdes.
  • Passo. Suponha que existem {n} marcianos numerados de {1} até {n}. Removendo um marciano {m\in \{1,\dots,n\}} de Marte temos, pela hipótese do passo indutivo, que os {n-1} marcianos restantes são verdes. Resta descobrir a cor do marciano {m}. Removendo um marciano {\ell \in \{1,\dots,n\}} com {\ell \neq m} temos, pelo mesmo motivo, que os marcianos restantes, inclusive {m}, são verdes. Portanto, todos os marcianos {1,\dots,n} são verdes.

    Descubra se há algo de errado nessa demonstração.

  • Exercício 2 Descubra uma falha na prova: todos os números naturais são iguais.

    Denotamos por {\max(a,b)} o maior número natural dentre {a} e {b}. Vamos mostrar por indução que se {\max(a,b)=n} então {a=b}.

  • Base. Se {\max(a,b)=0} então {a=b=0}.
  • Passo. Suponha que se {\max(a,b)=k-1} então {a=b}.

    Vamos mostrar que

    se {\max(a,b)=k+1} então {a=b}.

    Suponha que {\max(a,b)=k+1}. Então {\max(a-1,b-1)=k} e pela hipótese indutiva {a-1=b-1}, portanto {a=b}.

  • Exercício 3 Prova de {6n=0} para todo {n \geq 0}.

  • Base. Se {n=0} então {6n=0}.
  • Passo. Suponha que {6k=0} para todo {0\leq k<n}. Tome {a,b <n} números naturais tais que {n=a+b}. Portanto, {6n= 6a+6b} e pela hipótese indutiva {6a=0} e {6b=0}, logo {6n=0}. Onde está o erro?

  • Exercício 4 Prove por indução

    1. Para {n\geq 1} existem {2^n} seqüências de {n} bits {(n\geq 1)}.

    2. Para {n\geq 0}, a árvore binária completa com {n} níveis tem {2^n -1} nós.

    3. Para {n\geq 1}, a representaçõa binária de {n} tem {\lfloor \log_2(n)\rfloor+1} bits.

    Exercício 5 Um grupo de pessoas está em uma fila pra comprar entradas para um cinema. A primeira pessoa na fila é uma mulher e a última é um homem. Aplique a prova por indução para mostrar que em algum ponto da fila uma mulher está diretamente na frente de um homem.

    Exercício 6 A população de um pais cresce a taxa de {2\%} ao ano. Descubra uma recorrência para a população após {n} anos se atualmente a população é {P_0}.

    Exercício 7 Seja {K(n)} o número de seqüências formadas por {n} símbolos do conjunto {\{0,1,2,\dots,k-1\}}, para {n\geq 1} e {k\geq 2}. Escreva uma recorrência para {K(n)} e mostre, por indução, que {K(n)=k^n}.

    Exercício 8 Escreva uma recorrência que expresse o número de seqüências de {n\geq 1} digitos tomados do conjunto {\{0,1,2,3,4\}} com pelo menos um {2} e o primeiro {2} ocorre antes do primeiro {0} (pode não ocorrer {0}‘s).

    Exercício 9 Considere o seguinte algoritmo recursivo que recebe como entrada {n\in \mathbb{N}} diferente de 0:

    Fat(n) { 
         Se n=1 devolva 1 
          senão devolva n*Fat(n-1) }
    

    Seja {M(n)} o número de multiplicações feitas pelo algoritmo tendo {n} como entrada.
    (a) Escreva a recorrência para {M(n)} e
    (b) encontre sua fórmula fechada.

    Deixe uma resposta

    Preencha os seus dados abaixo ou clique em um ícone para log in:

    Logotipo do WordPress.com

    Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

    Imagem do Twitter

    Você está comentando utilizando sua conta Twitter. Sair / Alterar )

    Foto do Facebook

    Você está comentando utilizando sua conta Facebook. Sair / Alterar )

    Foto do Google+

    Você está comentando utilizando sua conta Google+. Sair / Alterar )

    Conectando a %s