Indução Matemática

Considere a afirmação:

\begin{align*} 1+2+3+4+...+n=\frac{n(n+1)}{2} \end{align*}

Verifique que para $n = 1$ a equação é verdadeira. Verifique que o mesmo também é verdade para $n = 2$, para $n = 3$ e assim sucessivamente. O problema é: como provar que a equação é verdadeira para qualquer $n$? Em outras palavras, como provar que a soma dos $n$ primeiros números inteiros a partir de $1$ é igual a $n(n+1)/2$?

Antes disso, por este conteúdo estar inserido no contexto da Lógica Matemática, é importante representar o problema logicamente.

Seja $P(n)$ um predicado definido para $n$ inteiros e $n_0$ seja um inteiro fixo. Suponha que as seguintes afirmações sejam verdadeiras:

  • $P(n_0) = V$
  • Para todos os inteiros $k \geq n_0$, se $P(n) = V$ então $P(n + 1) = V$

A segunda afirmação também pode ser vista como: se a equação é verdadeira para $n=k$ então também é verdadeira para $n=k+1$.

Considerando a proposição $p$ como $P(k)$ e $q$ como $P(k + 1)$, temos: $p \rightarrow q$.

Um entendimento chave aqui é que o inteiro $n + 1$ é o imediatamente posterior ao inteiro $n$. Assim, para $n = k$, $P(n) = P(k - 1)$ e $P(n + 1) = P(k)$. Assim, também é válido supor que se $P(k - 1) = V$ então $P(k) = V$, ou seja $P(k - 1) \rightarrow P(k)$.

Para provar a afirmação do início do capítulo usando indução matemática, usamos dois passos:

Passo base

O passo base consiste em provar que $P(n)$ é verdadeira para um $n$ bem pequeno (também chamado menor). Vamos assumir que isso seja verdade para $n = 1$ (que é o início da sequência). É fácil mostrar que:

\begin{align*} 1 = \frac{1(1+1)}{2} = 1 \end{align*}

Portanto, $P(1)$ é verdadeiro.

Passo de indução

Para provar que $P(n = k)$ é verdadeira, assumimos que se a equação é verdadeira para $P(n = k - 1)$ (isso também é chamado de hipótese indutiva):

\begin{align*} 1 + 2 + ... + (k - 1) &= \frac{(k-1)((k-1)+1)}{2} \\ &= \frac{((k-1)*(k-1))+(k-1)}{2} \\ &= \frac{(k^2-k-k+1)+(k-1)}{2} \\ &= \frac{(k^2-2k+1)+(k-1)}{2} \\ &= \frac{k^2-2k+1+k-1}{2} \\ &= \frac{k^2-k}{2} \\ &= \frac{k*k-k}{2} \\ &= \frac{k(k-1)}{2} \end{align*}

então é verdadeira para $P(n = k)$:

A técnica é adicionar $k$ a ambos os lados da equação, mantendo a igualdade:

\begin{align*} 1+2+...+(k-1)+k &= \frac{k(k-1)}{2}+k \\ &= \frac{k(k-1)}{2}+\frac{2k}{2} \\ &= \frac{k(k-1)+2k}{2} \\ &= \frac{(k^2-k)+2k}{2} \\ &= \frac{k^2-k+2k}{2} \\ &= \frac{k^2+k}{2} \\ &= \frac{k*k+k}{2} \\ &= \frac{k(k+1)}{2} \end{align*}

Assim, provamos por indução matemática que $n(n+1)/2$ é válida para todo $n \geq 1$.

Exercício

Use a indução matemática para provar que

\begin{align*} 1 + 3 + 5 + ... + (2k - 1) = k^2 \end{align*}

para cada inteiro positivo $k$.

Qual o passo base e qual o passo de indução?

Indução e recursão (recursividade)

Na recursão, uma função chama a si mesma. Na prova por indução matemática, no passo indutivo, provamos uma propriedade para uma dimensão de tamanho $n$ supondo que a propriedade seja verdadeira para dimensões menores.

Por exemplo, usando a equação do início do capítulo:

\begin{align*} s(n)=1+2+...+n=\frac{n(n+1)}{2} \end{align*}

o programa recursivo funciona chamando a si mesmo para provar que $s(n-1)=(n-1)n/2$.

O caso básico (passo base) é usado quando a recursão não funciona mais (critério de parada). O programa a seguir exemplifica isso.

ProvaSoma(n) // suponha que n seja um inteiro positivo. // este é um programa recursivo que aceita n e imprime uma prova detalhada // mostrando que s(n) = n*(n+1)/2. se (n == 1) então imprima "Notamos que" imprima " s(1) = 1 = 1*2/2, de modo que a fórmula está correta para n=1" senão imprima "Para provar que s(" + n + ") = " + n + "*" + n+1 + "/2" imprima " primeiro provamos que " imprima " s(" + n-1 + ") = " + n-1 + "*" + n + "/2" ProvaSoma(n - 1) imprima "Tendo aprovado s(" + n-1 + ") = " + n-1 + "*" + n + "/2" + (n-1)*n/2 + " somamos " + n imprima " ao primeiro e ao último valores, obtendo, " imprima " s(" + n + ") = " + ((n-1)*n/2 + n) + "." imprima " Isso é igual a " + n + "*" + n+1 + "/2" imprima " de modo que a fórmula seja correta para n=" + n + "." fim-se

Exercício: Escolha uma linguagem de programação de sua preferência e implemente o código anterior. Verifique o valor de "ProvaSoma(n)" para alguns valores de n.