Indução e recorrências

Verificar uma propriedade para os primeiros dez naturais não prova que vale para todos. A indução liga os casos: verificamos o início e provamos que o resultado passa aos seguintes. A hipótese de indução é uma hipótese local sobre $k$; não é a afirmação universal que queremos provar.

Indução simples

Para provar $P(n)$ para todo o inteiro $n\ge n_0$:

1. Prova $P(n_0)$, o caso base.
2. Toma um $k\ge n_0$ arbitrário e assume $P(k)$.
3. Com essa hipótese, prova $P(k+1)$.

O terceiro passo tem de valer para todos os $k$ a partir da base. Provar $P(k+1)\Rightarrow P(k)$ seria propagar no sentido errado.

A boa ordenação de $\mathbb N$ explica o método. Se houvesse casos falsos, haveria um primeiro caso falso $m$. A base impede $m=n_0$ e o passo a partir de $P(m-1)$ impede o caso seguinte de ser falso. Assim, não há primeiro caso falso.

Soma dos quadrados

Vamos provar, para $n\ge0$:

$$\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}6.$$

Para $n=0$, a soma vazia vale 0 e a fórmula também. Assume agora a igualdade para $n=k$. Separamos o termo novo e usamos essa hipótese:

$$\begin{aligned} \sum_{i=1}^{k+1}i^2 &=\sum_{i=1}^{k}i^2+(k+1)^2\\ &=\frac{k(k+1)(2k+1)}6+(k+1)^2\\ &=\frac{(k+1)(2k^2+7k+6)}6\\ &=\frac{(k+1)(k+2)(2k+3)}6. \end{aligned}$$

A última expressão é a fórmula para $k+1$, porque $2(k+1)+1=2k+3$. Não assumimos a soma até $k+1$; derivámo-la da soma até $k$.

Divisibilidade e desigualdades

Para mostrar $4\mid(5^n-1)$ para $n\ge0$, a base é $5^0-1=0$. No passo, assume $5^k-1=4q$, de modo que:

$$5^{k+1}-1=5(5^k-1)+4=4(5q+1).$$

Como $5q+1$ é inteira, a divisibilidade fica provada.

Numa desigualdade, conserva a direção das comparações. Para $2n+1\le2^n$ quando $n\ge3$, a base é $7\le8$. Se $2k+1\le2^k$:

$$2^{k+1}\ge2(2k+1)=4k+2\ge2k+3=2(k+1)+1,$$

onde a segunda desigualdade usa $k\ge3$, em particular $2k\ge1$. Indica essa condição em vez de a esconderes num salto algébrico.

Bases que faltam e hipóteses demasiado fortes

Uma prova que usa $P(k-2)$ precisa de garantir que esse caso já está no intervalo conhecido. Não basta verificar a primeira base se o passo só começa três valores depois.

Na falsa prova de que todos os cavalos têm a mesma cor, divide-se um grupo de $k+1$ cavalos em dois grupos de $k$ e usa-se um cavalo comum para comparar as cores. Para $k=1$, os dois grupos não têm cavalo comum. O passo falha de 1 para 2, precisamente onde precisava de funcionar.

Uma prova também pode ser válida sem usar a hipótese de indução: uma demonstração direta de $P(k+1)$ para um $k$ arbitrário chega. Usar a hipótese não é uma obrigação formal; assumir a tese ou omitir o passo é que invalida a prova.

Indução forte

Na indução forte, para provar $P(k+1)$ assumimos todos os casos $P(n_0),\ldots,P(k)$. Isto permite usar uma decomposição cujo tamanho não é necessariamente $k$.

Todo o inteiro $n\ge2$ é produto de primos. A base 2 é primo.

Para $k+1$, se for primo, já temos um produto com um fator. Se for composto, $k+1=ab$ com $2\le a,b\le k$. A hipótese forte dá fatorizações de $a$ e $b$, que juntamos. Só conhecer a fatorização de $k$ não forneceria esses dois resultados diretamente.

Vários casos base

Com moedas de 3 e 5 cêntimos podemos formar todos os valores inteiros $n\ge8$. As bases são:

$$8=3+5,\qquad9=3+3+3,\qquad10=5+5.$$

Para $n\ge11$, o valor $n-3\ge8$ já pode formar-se pela hipótese forte. Acrescentamos uma moeda de 3. As três bases cobrem os restos possíveis módulo 3 e permitem que o primeiro passo, de 10 para 11, use 8.

Indução em grafos

O parâmetro da indução pode contar vértices. Para provar que $C_{2n}$ é bipartido para $n\ge2$, a base é $C_4$, com partes alternadas de dois vértices.

No passo, toma um ciclo $C_{2n+2}$ e reduz o problema ao ciclo menor em três movimentos:

1. Retira dois vértices consecutivos $x,y$ e liga os seus vizinhos exteriores $u,v$ com uma aresta auxiliar. O ciclo restante tem $2n$ vértices, logo é bipartido pela hipótese, e a aresta nova obriga $u,v$ a cores diferentes.
2. Repõe o percurso $u,x,y,v$ e retira a aresta auxiliar. Atribui a $x$ a cor de $v$ e a $y$ a cor de $u$.
3. Confere as três arestas $u,x$, $x,y$ e $y,v$: cada uma liga cores distintas, e o restante ciclo conserva a coloração da hipótese.

Assim, a bipartição de $C_{2n+2}$ constrói-se a partir da do ciclo menor. Retirar só um vértice e fechar o percurso daria um ciclo ímpar, ao qual a hipótese sobre ciclos pares não se aplica. Citar diretamente que não há ciclos ímpares prova o resultado por outro método, mas não constrói este passo indutivo.

Funções recursivas

Uma definição recursiva precisa de casos base e regras que atinjam entradas já menores. Por exemplo:

$$f(n)=\begin{cases} 0,&n=0,\\ 4f(n/2),&n>0\text{ par},\\ f(n-1)+2n-1,&n\text{ ímpar}. \end{cases}$$

A função está definida nos naturais e cada chamada diminui o argumento. Vamos provar $f(n)=n^2$ por indução forte. A base $f(0)=0$ serve. Para $n>0$:

• Se é par, $n/2<n$, logo $f(n)=4(n/2)^2=n^2$.
• Se é ímpar, $n-1<n$, logo $f(n)=(n-1)^2+2n-1=n^2$.

A prova usa a hipótese para um argumento que pode estar muito antes do imediato. Para seguir a definição em $n=6$, as chamadas descem assim:

$$f(6)\ \longrightarrow\ f(3)\ \longrightarrow\ f(2)\ \longrightarrow\ f(1)\ \longrightarrow\ f(0).$$

Os valores regressam na ordem inversa:

Chamada	Regra aplicada	Valor
$f(0)$	Base	0
$f(1)$	$f(0)+2\cdot1-1$	1
$f(2)$	$4f(1)$	4
$f(3)$	$f(2)+2\cdot3-1$	9
$f(6)$	$4f(3)$	36

Este cálculo explica uma chamada concreta. A prova forte justifica todos os naturais, incluindo valores não listados na tabela; entradas negativas não têm imagem, pois a definição só cobre $n\ge0$.

Sequências e recorrências

Uma sequência associa um valor a cada índice. Uma recorrência define termos por termos anteriores, por exemplo:

$$a_1=1,\quad a_2=4,\quad a_n=2a_{n-1}-a_{n-2}\quad(n\ge3).$$

Os primeiros valores são $1,4,7,10$. Conjeturamos $a_n=3n-2$, mas a lista não prova a fórmula. Como a recorrência usa dois termos anteriores, verificamos as bases 1 e 2. Para $n\ge3$, usando a hipótese para os dois termos anteriores:

$$a_n=2(3(n-1)-2)-(3(n-2)-2)=3n-2.$$

Torres de Hanói

As Torres de Hanói têm três pinos e discos de tamanhos distintos. Movemos um disco de cada vez, sempre o do topo, sem colocar um maior sobre um menor. Para mover uma torre de $n$ discos, movemos os $n-1$ menores para o pino auxiliar, movemos o maior e movemos os menores para cima dele.

Se $H_n$ é o número de movimentos deste algoritmo:

$$H_0=0,\qquad H_n=2H_{n-1}+1\quad(n\ge1).$$

Somando 1, $H_n+1=2(H_{n-1}+1)$. Logo, $H_n+1=2^n$ e $H_n=2^n-1$.

Ver por que o algoritmo é mínimo

Para provar o mínimo, fazemos indução em $n$. A torre vazia precisa de zero movimentos.

1. Antes do primeiro movimento do maior disco, os $n-1$ menores têm de estar todos no terceiro pino, fora da origem e do destino desse movimento.
2. Depois do último movimento do maior para o destino final, esses menores têm de passar do terceiro pino para cima dele.
3. Cada fase exige pelo menos $H_{n-1}$ movimentos pela hipótese. Entre as fases há pelo menos um movimento do maior.

Logo qualquer solução usa pelo menos $2H_{n-1}+1$. O algoritmo atinge esse limite.

Recorrências lineares de primeira ordem

Para $a_n=ra_{n-1}+b$, $n\ge1$, com $a_0$ dado, expandimos três termos sem mudar os dados:

$$\begin{aligned} a_1&=ra_0+b,\\ a_2&=r(ra_0+b)+b=r^2a_0+rb+b,\\ a_3&=r(r^2a_0+rb+b)+b=r^3a_0+r^2b+rb+b. \end{aligned}$$

Cada termo constante sofre uma multiplicação por $r$ em cada passo posterior à sua entrada. O último fica sem essa multiplicação. A soma geométrica reúne as $n$ contribuições:

$$a_n=r^na_0+b\sum_{j=0}^{n-1}r^j.$$

Se $r\ne1$:

$$a_n=r^na_0+b\frac{r^n-1}{r-1}.$$

Se $r=1$, a soma tem $n$ parcelas iguais a 1 e $a_n=a_0+nb$.

Para $a_0=2$ e $a_n=3a_{n-1}+1$, obtemos $a_n=(5\cdot3^n-1)/2$. Substituir $n=0$ e a fórmula na recorrência confere ambas as condições.

Equação característica

Para uma recorrência homogénea de segunda ordem com coeficientes constantes:

$$a_n=\alpha a_{n-1}+\beta a_{n-2},\qquad n\ge2,$$

procurar soluções $a_n=r^n$, com $r\ne0$, dá $r^n=\alpha r^{n-1}+\beta r^{n-2}$. Dividimos por $r^{n-2}$ e obtemos a equação característica $r^2-\alpha r-\beta=0$. Quando as duas raízes distintas $r_1,r_2$ são não nulas, a solução tem a forma $a_n=Ar_1^n+Br_2^n$. Determinamos $A,B$ pelas duas condições iniciais.

Para $a_0=2,a_1=5$ e $a_n=3a_{n-1}-2a_{n-2}$, a equação é $(r-1)(r-2)=0$. Assim:

$$a_n=A+B2^n,\qquad A+B=2,\qquad A+2B=5.$$

Daqui $B=3,A=-1$ e $a_n=3\cdot2^n-1$. Os primeiros valores são $2,5,11,23$, coerentes com a recorrência.

Para uma raiz dupla não nula $r$, a forma é $(A+Bn)r^n$. Por exemplo, $a_n=2a_{n-1}-a_{n-2}$ tem raiz dupla 1 e dá uma sequência da forma $A+Bn$. O fator $n$ fornece a segunda solução independente. O método acima não se aplica diretamente a recorrências não homogéneas, nem dispensa tratar casos degenerados com raiz zero.