Indução e recorrências

Como provas uma afirmação sobre todos os naturais se não podes testá-los um a um? A indução responde: prova o primeiro caso e prova que cada caso implica o seguinte, como uma fila de dominós onde derrubar o primeiro deita todos abaixo. E quando um problema se define à custa de casos anteriores (fatorial, juros, algoritmos recursivos), uma relação de recorrência modela-o e a indução prova a solução.

Indução simples: os três passos

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

1. Base: prova $P(n_0)$.
2. Hipótese de indução: assume $P(k)$ para um $k$ genérico.
3. Passo indutivo: prova $P(k+1)$ usando a hipótese.

Exemplo: $2^0 + 2^1 + \dots + 2^{n-1} = 2^n - 1$ para $n \ge 1$.

• Base ($n = 1$): o lado esquerdo é $2^0 = 1$ e o direito é $2^1 - 1 = 1$. Verdadeiro.
• Hipótese: assume $\sum_{i=0}^{k-1} 2^i = 2^k - 1$.
• Passo: $\sum_{i=0}^{k} 2^i = (\sum_{i=0}^{k-1} 2^i) + 2^k = (2^k - 1) + 2^k = 2 \cdot 2^k - 1 = 2^{k+1} - 1$. É $P(k+1)$.

Há uma leitura bonita em binário: o lado esquerdo é o número de $n$ bits todos a 1 ($111\dots1_2$), e $2^n$ é $100\dots0_2$; somar 1 ao primeiro dá o segundo, o que confirma a igualdade.

O que pode correr mal

Três falhas típicas, todas elas pedidas em exercícios de “encontra o erro”:

• Base em falta ou falsa. Sem base, o passo indutivo prova apenas “se um dominó cai, o seguinte cai”, com a fila toda de pé. A indução sem base não prova nada.
• Usar a hipótese onde ela não chega. Na passagem de $k$ para $k+1$ tens de invocar $P(k)$ explicitamente. Se a prova de $P(k+1)$ nunca usa a hipótese, desconfia: ou a afirmação é trivial, ou há erro.
• Falsa indução. A “prova” de que todos os cavalos têm a mesma cor assume que dois conjuntos de $k$ cavalos com $k-1$ em comum partilham a cor, o que falha na passagem de 1 para 2 (a interseção é vazia). O passo tem de valer para todo o $k$, incluindo o primeiro.

Indução forte

Na indução forte, a hipótese assume $P(j)$ para todos os $j$ de $n_0$ até $k$, e prova $P(k+1)$. É preciso quando o caso $k+1$ depende de vários anteriores, não só do imediato.

Exemplo: todo o inteiro $n \ge 2$ é primo ou produto de primos.

• Base: $n = 2$ é primo.
• Hipótese forte: assume que todos os inteiros de $2$ a $k$ fatorizam em primos.
• Passo: considera $k+1$. Se $k+1$ é primo, está feito. Se é composto, $k+1 = a \cdot b$ com $2 \le a, b \le k$; pela hipótese, $a$ e $b$ fatorizam em primos, e juntando as fatorizações obténs a de $k+1$.

Com indução simples isto emperrava, porque $a$ e $b$ não são necessariamente $k$. Sempre que a decomposição “salta para trás” mais de uma casa, usa a forte.

A indução (simples ou forte) equivale ao princípio da boa ordenação: todo o conjunto não vazio de naturais tem mínimo. Se $P$ falhasse algures, o conjunto dos contraexemplos teria um mínimo $m$, e o passo indutivo aplicado a $m - 1$ contradiria a minimalidade.

Sequências: três formas de definir

Uma sequência é uma função de um conjunto infinito de inteiros (normalmente $\mathbb{N}$) para $\mathbb{R}$. Pode definir-se:

• Por lista: $1, 4, 9, 16, \dots$ (exige adivinhar o padrão).
• Recursivamente: $a_1 = 2$, $a_{k+1} = 2a_k$ (cada termo à custa dos anteriores).
• Por fórmula explícita: $a_n = 2^n$ (cálculo direto).

As clássicas: a aritmética ($a_{k+1} = a_k + d$, termo geral $a_n = a + (n-1)d$, soma $S_n = n(2a + (n-1)d)/2$) e a geométrica ($a_{k+1} = r a_k$, termo geral $a_n = a r^{n-1}$, soma $S_n = a(1-r^n)/(1-r)$ para $r \ne 1$). Exemplo: $-7, -4, -1, 2, 5, 8, \dots$ é aritmética de razão $3$; $1, 2, 4, 8, \dots$ é geométrica de razão $2$.

O problema central: dada a definição recursiva, descobrir a explícita. É o que resolve a teoria das recorrências.

Relações de recorrência de primeira ordem

O modelo do empréstimo: capital em dívida $c_n$ no mês $n$, juro mensal $J$, prestação constante $P$, capital inicial $C$. Cada mês o capital rende juros e abate a prestação:

$c_n = (1+J)c_{n-1} - P, \quad n \ge 1, \quad c_0 = C.$

Resolve-se em duas partes: a solução da homogénea ($q_n = d(1+J)^n$) mais uma solução particular constante ($p_n = b$ com $b = (1+J)b - P$, logo $b = P/J$). A solução geral é $c_n = d(1+J)^n + P/J$, e $c_0 = C$ dá $d = C - P/J$:

$c_n = \left(C - \frac{P}{J}\right)(1+J)^n + \frac{P}{J}.$

Exemplo numérico: $C = 3500$ euros, TAN $26\%$ (logo $J = 0{,}26/12 \approx 0{,}021667$), $N = 12$ meses. Impondo $c_{12} = 0$ obtém-se $P = C \cdot J(1+J)^{12}/((1+J)^{12}-1) \approx 334{,}36$ euros. Podes confirmar a fórmula simulando mês a mês:

C, J, N = 3500.0, 0.26 / 12, 12
P = C * J * (1 + J) ** N / ((1 + J) ** N - 1)
print(f"prestacao = {P:.2f}")
saldo = C
for mes in range(1, N + 1):
    saldo = (1 + J) * saldo - P
print(f"saldo final = {saldo:.6f}")  # proximo de 0

Recorrências lineares de segunda ordem

Uma recorrência linear homogénea de segunda ordem tem a forma $a_n = A a_{n-1} + B a_{n-2}$. Tenta soluções da forma $a_n = r^n$: substituindo e dividindo por $r^{n-2}$ obténs a equação característica $r^2 = Ar + B$. Se ela tem duas raízes distintas $r_1, r_2$, a solução geral é $a_n = c_1 r_1^n + c_2 r_2^n$; as condições iniciais fixam $c_1, c_2$.

Exemplo resolvido: $a_n = 5a_{n-1} - 6a_{n-2}$ com $a_0 = 0$ e $a_1 = 1$.

1. Equação característica: $r^2 - 5r + 6 = 0$, raízes $r = 2$ e $r = 3$.
2. Solução geral: $a_n = c_1 2^n + c_2 3^n$.
3. $a_0 = 0$ dá $c_1 + c_2 = 0$; $a_1 = 1$ dá $2c_1 + 3c_2 = 1$. Resolvendo: $c_1 = -1$, $c_2 = 1$.
4. Solução: $a_n = 3^n - 2^n$.

Verifica por indução os primeiros termos: $a_2 = 9 - 4 = 5$ e a recorrência dá $5 \cdot 1 - 6 \cdot 0 = 5$; $a_3 = 27 - 8 = 19$ e $5 \cdot 5 - 6 \cdot 1 = 19$. Confere.

Os casos especiais: raiz dupla $r$ (solução $a_n = (c_1 + c_2 n) r^n$) e termo independente não nulo (procura-se uma particular com a forma do termo independente, como no empréstimo). A sequência de Fibonacci, $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$, resolve-se pelo mesmo método, com equação $r^2 = r + 1$.

Indução prova correção de programas

A mesma técnica prova que um ciclo faz o que promete, via invariante. No cálculo iterativo do fatorial (fat acumulador, i contador), o invariante é: no fim de cada iteração, $fat = i!$. Vale antes do ciclo ($i = 1$, $fat = 1$) e cada iteração preserva-o ($fat \cdot (i+1) = (i+1)!$). Quando o ciclo termina com $i = n$, tens $fat = n!$. Base e passo, outra vez: invariantes são indução disfarçada, e voltarão em AED e noutras cadeiras.