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:
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?
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.