Indução Matemática - Visão Geral

Agora vamos de fato ao que interessa, neste post darei uma visão geral da indução matemática. É com base no que apresentarei aqui que faremos todas as nossas análises nos próximos posts.

Indução Matemática

Poderosa técnica de prova, usada largamente na matemática para provar a corretude de teoremas. Na Ciência da Computação é utilizada para provar a corretude de algoritmos, além de ser uma super ferramenta que auxilia a construção de algoritmos e a descrição indutiva de estruturas de dados.

Esquema para a prova de um teorema
Seja T um teorema que queremos provar. Suponha que T inclui um parâmetro n cujo valor pode ser qualquer número natural. Ao invés de provarmos que T vale para todos os valores de n, nós provaremos as seguintes condições:

1. T vale para n = 1.
2. Para todo n > 1, se T vale para n - 1, então T vale para n.

A condição 1 é fácil de provar. Basta verificar a validade de T para valores pequenos de n, geralmente verificamos para n = 0 ou n = 1.

Provar a condição 2 é mais fácil que provar o teorema diretamente, então nós podemos supor que T vale para n - 1. Esta suposição é chamada de Hipótese de Indução (e será muito usada em nossas explicações aqui no blog).

O esquema acima decorre do Princípio da Indução que é enunciado da seguinte forma:

•  Se a asserção P, com parâmetro n, é verdade para n = 1, e se, para todo n > 1, a verdade de P para n - 1 implica na verdade de P para n, então P é verdade para todos os números naturais.

Teorema 1: A soma dos n primeiros números naturais é S(n) = n(n + 1)/2.
A prova é por indução em n.
Caso Base: Vamos verificar a validade do teorema para n = 1.
                   S(1) = 1(1+1)/2
                           = 1

Hipótese de Indução: Vamos assumir que o teorema vale para a soma de n - 1 números.
                   S(n - 1) = (n - 1)(n - 1 + 1)/2
                                = (n - 1)(n)/2

Agora no passo indutivo vamos extender a solução, mostrando que o teorema vale para n. É importante lembrar que a utilização da hipótese de indução neste passo é obrigatória.
                  S(n) = S(n - 1) + n
                         = n (n + 1) / 2

Agora já podemos derivar o nosso primeiro algoritmo usando indução:

#include <iostream>

using namespace std;

int soma(int n)
{
  if(n == 1) // caso base
    return n;
  else
    return soma(n - 1) + n; //passo indutivo, vejam a hipótese de indução "soma(n - 1)"
}

int main()
{
  int n;
  cin >> n;
  cout << soma(n) << endl;
  return 0;
}

O programa acima possui complexidade O(n), no entanto, é possível fazer melhor. A aplicação direta da fórmula resolve o problema em tempo O(1), ou seja, gastando apenas algumas operações constantes. No entanto, o objetivo do exemplo nesta introdução foi mostrar a relação direta que existe entre a indução e a construção de algoritmos.

Um problema de dificuldade razoável do Spoj é o Cards. Vale a pena tentar o/

http://www.spoj.pl/problems/CRDS/