Prova indutiva: Se n é um inteiro maior que 1, então n pode ser escrito como o produto de primos

Neste post, vamos provar que todo número pode ser escrito como o produto de números primos. Usaremos indução forte, ou seja, não assumiremos a verdade da proposição P apenas para n-1 (indução fraca), mas para todo inteiro menor que n, inclusive n-1. É importante lembrar que as formas forte e fraca são equivalentes, mas as vezes, optar por uma das formas facilita a prova. Confira nosso post sobre os tipos de indução aqui.

              P(n): Todo número inteiro n > 1 pode ser escrito como o produto de números primos.

A prova é por indução em n:

• Caso Base: para n = 2, temos que 2 é primo, logo é o único fator primo.
• Hipótese de Indução: vamos assumir que para $2 \le j \le n-1$, j pode ser escrito como o produto de números primos.
• Caso Geral: Devemos considerar dois caso. Se n for primo, então n pode ser escrito como o produto de um primo, ele mesmo. Caso n seja composto, ou seja, n = a * b com $2 \le a \le b \le n-1$, sabemos que por hipótese de indução a e b podem ser escritos como o produto de primos. Como n = a * b, a decomposição de n em fatores primos, é simplesmente a multiplicação de todos os fatores de a pelos fatores de b.      C.Q.D

@inductioncode

Indução e diferenciação: A derivada da função polinomial

Neste post, vamos usar a indução matemática para provar que a derivada da função $f(x) = x^n$é $f'(x) = nx^{n-1}$. Como podemos perceber, precisamos escolher a variável na qual a indução será aplicada, pois a fórmula envolve as variáveis x e n. Aplicaremos indução em n porque a indução só pode ser aplicada sobre os números naturais, e a variável x é real.

Prova por indução em n:

• Caso Base: para n = 1, temos que $\frac{d  x}{dx} = 1*x^{1-1} = 1$, e de fato, a derivada da função identidade $f(x) = x$ é $f'(x) = 1$. 
• Hipótese de Indução: para n = k-1, vamos assumir que a derivada da função $f(x) = x^n$ é $f'(x) = (k-1)x^{k-2}$.
• Caso Geral: Agora, vamos mostrar que  $f'(x) = (k-1)x^{k-1}$ para n = k:
                                           $\frac{d  x^k}{dx} = kx^{k-1}$
                                           {pela regra da cadeia}
                                           $\frac{d  x^k}{dx} = \frac{d  x*x^{k-1}}{dx}$
                                           $                              = 1*x^{k-1} + x*(k-1)x^{k-2}$
                                           $                              = x^{k-1} +(k-1)x^{k-1}$
                                           $                              = (1 + k - 1)x^{k-1}$
                                           $                              = kx^{k-1}$   C.Q.D.

Apesar de uma abordagem puramente matemática, treinar a elaboração de provas através da indução matemática é um exercício fundamental para que possamos construir algoritmos usando indução com mais facilidade.

Inserindo elementos em uma sequência ordenada

Neste post, vamos descrever indutivamente um algoritmo para inserir um elemento em uma sequência ordenada. Utilizaremos a linguagem Haskell, e em posts posteriores apresentaremos implementações em Python e Scala.

Descrição indutiva:

• Caso Base: Inserir um elemento em uma sequência vazia é trivial.
• Hipótese de Indução: Vamos assumir que sabemos como inserir um elemento em uma sequência com n-1 elementos.
• Caso Geral: Simples, basta verificar se o elemento que desejamos inserir é maior ou menor que o primeiro elemento da lista, caso seja maior, entregamos o elemento e o restante da lista para a hipótese de indução, caso seja menor que o primeiro elemento, basta colocá-lo no início da lista ordenada.

A implementação em Haskell segue exatamente a descrição indutiva apresentada acima.

• Implementação em Haskell

insert :: [Int] -> Int -> [Int]
insert [] a = [a]
insert (x:xs) a 
  | (a < x)   = a:(x:xs)
  | otherwise = x:(insert xs a)

Como podemos perceber, utilizar uma linguagem funcional ajuda no processo de abstração e resolução dos problemas. Inductioncode disponibilizará em breve um editorial que fará um comparativo entre os paradigmas funcional e imperativo.

Prova Indutiva: $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n}^2 = F{\tiny n} \times F{\tiny n+1}$

A sequência 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .... é conhecida como série de Fibonacci e foi definida formalmente aqui. Os números de Fibonacci possuem várias propriedades interessantes, agora vamos apresentar uma delas, provando por indução que

                                                           $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n}^2 = F{\tiny n} \times F{\tiny n+1}$

A prova é por indução em n:

• Caso Base: Para n = 1, $F{\tiny 1}^2 = F{\tiny 1} \times F{\tiny 2}$.
• Hipótese de Indução: Vamos assumir que $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n-1}^2 = F{\tiny n-1} \times F{\tiny n}$.
• Caso Geral: No passo indutivo, basta adicionarmos o valor de $F{\tiny n}^2$ a soma dos primeiros n-1 elementos que definimos na hipótese de indução, ou seja

                                                     $F{\tiny n} \times F{\tiny n+1} = \overbrace{\underbrace{(F{\tiny n-1} \times F{\tiny n})}_\text{Hipótese de Indução} + F{\tiny n}^2}^{Caso Geral}$

                                                    $F{\tiny n} \times F{\tiny n+1} = F{\tiny n} \times (F{\tiny n-1} + F{\tiny n})$

                         {Por definição, sabemos que $F{\tiny n} = F{\tiny n-1} + F{\tiny n-2}$, logo $F{\tiny n-1} + F{\tiny n} = F{\tiny n+1}$}

                                                   $F{\tiny n} \times F{\tiny n+1} = F{\tiny n} \times F{\tiny n+1}$      C.Q.D.

Torres de Hanói: Computando o número de movimentações

Em posts anteriores, apresentamos a descrição indutiva para o problema das Torres de Hanói e provamos que o número mínimo de movimentações necessárias para resolver o problema é $2^n - 1$, onde n é o número de discos. Agora, vamos usar a descrição indutiva já discutida para calcular o número de movimentações necessárias, mas com um detalhe, o número de movimentações será calculado no momento em que as movimentações forem feitas. Nosso objetivo é apresentar o significado de "fortalecimento da hipótese de indução".

Fortalecer uma hipótese, significa assumir que ela realiza algo a mais quando comparada à hipótese original. Ou seja, além de assumirmos que a proposição P(n-1) é válida, também assumiremos uma condição C(n-1) e em seguida estenderemos nossa solução para P(n) e C(n).

Para um pleno entendimento do tema tratado aqui, não deixem de ler os posts:

• Torres de Hanói: O número mínimo de movimentações é $2^n-1$.
• Torres de Hanói.

Siga o Inductioncode no Twitter: Seguir @inductioncode

Descrição indutiva:

• Caso Base: para n = 0, temos que o número de movimentações é 0.
• Hipótese de Indução: vamos assumir que sabemos como mover n-1 discos, e como condição extra vamos assumir que o número de movimentações está armazenado em uma variável que chamaremos de numMoves.
• Caso Geral: No passo indutivo, vamos estender a solução para o caso geral. Para isso, após realizar uma movimentação, basta incrementar a variável numMoves.

A implementação que apresentaremos em Java, segue exatamente a ideia apresentada acima.

• Implementação em Java

public static int numMoves = 0;
static void hanoi(int n, char A, char B, char C) {
  if (n > 0) {
    hanoi(n - 1, A, C, B);
    System.out.println("Mova o disco " + n + " de " + A + " para " + B);
    numMoves++;
    hanoi(n - 1, C, B, A);
  }
}

Em breve, falaremos mais sobre o fortalecimento da hipótese de indução. Aguardem.
@inductioncode

Prova indutiva: n! > $2^n$ para n $\geq$ 4

Provaremos agora a desigualdade n! > $2^n$ para n $\geq$ 4. Mostraremos que a função fatorial cresce mais rápido que a função exponencial.

A prova é por indução em n:

• Caso Base: Para n = 4, temos que $4! > 2^4$.
• Hipótese de Indução: Vamos supor que $(n-1)! > 2^{n-1}$.
• Caso Geral: Agora basta utilizar o resultado obtido na hipótese de indução e estender a solução para o caso geral, assim temos que

                               $2*(n-1)! > 2*2^{n-1}$

                       $2*(n-1)! > 2^n$  

         {como 2*(n-1)! é menor que n!, para n = 4, podemos substituí-lo por n! e mantemos a desigualdade}

                   $n! > 2^n$   C.Q.D.

Descrição Indutiva: Busca Binária recursiva em Java

Neste post, vamos descrever indutivamente e discutir a complexidade da busca binária. Como veremos,    a busca binária é mais eficiente que a busca sequencial discutida no post Descrição indutiva: Busca sequencial recursiva em Java. No entanto, para que possamos aplicar a busca binária em um vetor (lista) é necessário que ele esteja ordenado.

Descrição Indutiva:

• Caso Base: Para um vetor com apenas um elemento, basta verificar se o elemento procurado é o elemento armazenado no vetor.
• Hipótese de Indução: Vamos assumir que a hipótese de indução sabe procurar o elemento desejado em um vetor com $\frac{n}{2}$ elementos.
• Caso Geral: Vamos procurar um elemento K no vetor. Para compor o caso geral, vamos dividir o vetor ao meio e verificar se o elemento central é maior ou menor que K. Caso o elemento central seja menor que K, então K poderá ser encontrado na segunda parte do vetor, caso contrário, o elemento K poderá ser encontrado na primeira parte do vetor.

A implementação em Java (ou em sua linguagem predileta) segue exatamente a descrição indutiva do problema.

• Implementação em Java

public class BinarySearch {

  public static int binarySearch(int vet[], int value, int left, int rigth) {
    int middle;
    if (left <= rigth) {
      middle = left + (rigth - left) / 2;
      if (vet[middle] == value)
      return middle;
    else if (vet[middle] > value)
      return binarySearch(vet, value, left, middle - 1);
    else
      return binarySearch(vet, value, middle + 1, rigth);
    }
    return -1;
}
  public static void main(String[] args) {
    int vet[] = { 1, 3, 4, 6, 78, 90 };
    System.out.println(binarySearch(vet, 3, 0, 5));
  }
}

Complexidade
A busca binária é muito eficiente, pois a cada passo descarta a metade do espaço de busca. A relação de recorrência que expressa a complexidade do algoritmo é: $T(n) = T(\frac{n}{2}) + 1$. Resolvendo a recorrência temos que a busca binária é O(log n).


Gostou da publicação? Sim? Então curta nossa fan page no Facebook e acompanhe nossas postagens.

@inductioncode