Relações de Recorrência: Definindo Sequências por si Mesmas

Você aplica \(1000\) reais a \(1\%\) ao mês: no mês seguinte tem \(1010\), depois \(1020{,}10\), depois \(1030{,}30\ldots\) Do outro lado, quem financia um carro sabe que o saldo devedor deste mês é o do mês anterior menos a parcela, mais os juros sobre o que ainda resta. Em ambos os casos, calcular o valor do mês 12 exige conhecer o do mês 11 — não há atalho direto. Sequências assim, onde cada termo depende dos anteriores, são chamadas de relações de recorrência.

Mas o conceito vai além das finanças. Quantos movimentos são necessários para resolver a Torre de Hanoi com \(n\) discos? Uma simples equação, \(T_n = 2T_{n-1} + 1\), contém a resposta completa. Esse é o poder das relações de recorrência: descrever uma sequência inteira a partir de uma regra local.

Neste artigo vamos definir formalmente o conceito, ver exemplos clássicos e aprender o método de substituição para obter fórmulas fechadas — expressões diretas que calculam o \(n\)-ésimo termo sem depender dos anteriores. Ao final, veremos também a equação característica, técnica que estende o repertório para recorrências de ordem 2.

Por que as Relações de Recorrência?

#

Sequências definidas em termos de si mesmas aparecem em toda a ciência da computação e matemática discreta:

• Análise de algoritmos recursivos — a complexidade do merge sort, do quicksort e da Torre de Hanoi é expressa naturalmente por recorrências; resolvê-las dá a notação \(O\) do algoritmo.
• Contagem combinatória — o número de caminhos num grid, triangulações de polígonos e partições de inteiros satisfazem recorrências que permitem calcular termos grandes a partir de pequenos.
• Modelagem de crescimento — populações de coelhos (Fibonacci), crescimento com juros compostos e modelos epidemiológicos básicos são todos relações de recorrência.
• Programação dinâmica — técnica que substitui recursão exponencial por memoização linear; a validade da abordagem depende de verificar que a recorrência tem subestrutura ótima.
• Linguagens formais e compiladores — gramáticas livres de contexto geram linguagens cujo número de derivações satisfaz recorrências; analisar sua complexidade usa as mesmas ferramentas deste artigo.

O Que é uma Relação de Recorrência?

#

Para determinar completamente a sequência, precisamos das condições iniciais — os valores de \(a_1, a_2, \ldots\) que servem como ponto de partida.

Exemplo simples: As somas parciais \(S_n = 1 + 2 + \cdots + n\) satisfazem

A cada passo, basta acrescentar \(n\) ao valor anterior.

Exemplo: Expressões Aritméticas Válidas

#

Considere expressões formadas por dígitos (\(0{-}9\)) e símbolos aritméticos (\(+,-,\times,\div\)), obedecendo duas regras: a expressão deve começar e terminar com dígito, e dois símbolos não podem aparecer consecutivamente. Chamamos essa sequência de “válida” no sentido sintático — as regras verificam apenas a estrutura da string, não o significado matemático. Assim, 5÷0 é contada como válida (obedece as duas regras), mesmo que a divisão por zero seja indefinida.

Por exemplo:

Seja \(N_k\) o número de expressões válidas de comprimento \(k\).

Condições iniciais: \(N_0 = 0\), \(N_1 = 10\) (os dígitos \(0{-}9\))

Construção da recorrência:

Para obter uma expressão de comprimento \(k\) a partir de expressões menores, há duas estratégias:

1. Acrescentar um dígito (10 opções) à direita de uma expressão de comprimento \(k-1\): contribuição \(10 N_{k-1}\)
2. Acrescentar símbolo + dígito (\(4 \times 10 = 40\) opções) à direita de uma expressão de comprimento \(k-2\): contribuição \(40 N_{k-2}\)

O diagrama a seguir sintetiza as duas estratégias e a fórmula resultante:

Calculando os primeiros termos:

A Sequência de Fibonacci: Problema dos Coelhos

#

O problema clássico de Fibonacci (1202): uma colônia de coelhos cresce segundo as regras:

• Começa com 1 par recém-nascido
• Todo par com ≥ 2 meses de vida produz 1 novo par por mês
• Nenhum coelho morre

Seja \(F_n\) o número de pares ao final do mês \(n\). Os pares no mês \(n\) são:

• Os que existiam no mês anterior (\(F_{n-1}\) pares)
• Os novos nascidos neste mês, que correspondem aos pares com ≥ 2 meses no mês anterior (\(F_{n-2}\) pares)

Ao final de 13 meses: 233 pares.

A árvore de famílias abaixo mostra como cada par adulto gera um novo par a cada mês, tornando visível por que \(F_n = F_{n-1} + F_{n-2}\):

flowchart TD
  subgraph m1 ["Mês 1 — F₁ = 1"]
    A["par A (novo)"]
  end
  subgraph m2 ["Mês 2 — F₂ = 1"]
    B["par A (adulto)"]
  end
  subgraph m3 ["Mês 3 — F₃ = 2"]
    C["par A"]
    D["par B (novo)"]
  end
  subgraph m4 ["Mês 4 — F₄ = 3"]
    E["par A"]
    F["par B (adulto)"]
    G["par C (novo)"]
  end
  subgraph m5 ["Mês 5 — F₅ = 5"]
    H["par A"]
    I["par B"]
    J["par C (adulto)"]
    K["par D (novo)"]
    L["par E (novo)"]
  end
  A --> B
  B --> C
  B -->|gera| D
  C --> E
  D --> F
  C -->|gera| G
  E --> H
  F --> I
  G --> J
  E -->|gera| K
  F -->|gera| L

Torre de Hanoi

#

O puzzle da Torre de Hanoi foi proposto por Édouard Lucas em 1883. São dados \(n\) discos de tamanhos diferentes empilhados em ordem decrescente em um eixo. O objetivo é transferir todos para outro eixo, usando um eixo auxiliar, obedecendo:

1. Mover apenas um disco por vez (sempre do topo)
2. Nunca colocar um disco maior sobre um menor

Seja \(T_n\) o número mínimo de movimentos para \(n\) discos.

A figura abaixo mostra o estado inicial (todos os discos no Peg 1) e o estado final desejado (todos no Peg 2) para \(n = 3\):

Exemplo concreto: n = 3

Antes de pensar em fórmulas, vamos ver o que acontece passo a passo com 3 discos. Cada seta na figura abaixo representa um único movimento — sempre o disco do topo de um eixo para o topo de outro, respeitando a regra de nunca colocar um disco maior sobre um menor. A leitura segue da esquerda para a direita na linha superior (Estados 0 → 3), desce para o Estado 4, e volta da direita para a esquerda na linha inferior (Estados 4 → 7):

Foram necessários exatamente 7 movimentos para transferir os 3 discos.

Encontrando o padrão recursivo

Olhando com atenção para os 7 movimentos, percebemos uma estrutura em três blocos:

• Movimentos 1–3 (Estados 0 → 3): os 2 discos menores migram do Peg 1 para o Peg 3, usando o Peg 2 como auxiliar — exatamente \(T_2 = 3\) movimentos.
• Movimento 4 (Estado 3 → 4): o disco maior vai sozinho do Peg 1 para o Peg 2 — 1 movimento.
• Movimentos 5–7 (Estados 4 → 7): os 2 discos menores migram do Peg 3 para o Peg 2, usando o Peg 1 como auxiliar — novamente \(T_2 = 3\) movimentos.

Total: \(T_3 = 3 + 1 + 3 = 7\). ✓

Esse mesmo raciocínio se aplica para qualquer \(n\): para mover \(n\) discos, sempre precisamos (1) resolver o problema de tamanho \(n-1\), (2) mover o disco maior, e (3) resolver novamente o problema de tamanho \(n-1\). O diagrama abaixo sintetiza esse algoritmo recursivo — cada bloco rotulado \(T_{n-1}\) representa um subproblema completo com vários movimentos individuais, não um único passo:

Formalizando:

Calculando os primeiros valores:

A árvore de chamadas de \(T(3)\) torna a recorrência visível: cada nó \(T(k)\) desdobra-se em dois filhos \(T(k-1)\) mais uma unidade, até atingir o caso base \(T(1) = 1\):

flowchart TD
  T3["T(3) = 7"]
  T2a["T(2) = 3"]
  M1["+1"]
  T2b["T(2) = 3"]
  T1a["T(1) = 1"]
  M2["+1"]
  T1b["T(1) = 1"]
  T1c["T(1) = 1"]
  M3["+1"]
  T1d["T(1) = 1"]
  T3 --> T2a & M1 & T2b
  T2a --> T1a & M2 & T1b
  T2b --> T1c & M3 & T1d

Método de Substituição

#

O método de substituição consiste em aplicar a relação de recorrência repetidamente, substituindo cada termo pela sua própria recorrência, até emergir um padrão geral.

Toda aplicação do método segue as mesmas cinco etapas:

O diagrama abaixo sintetiza o fluxo do método:

flowchart LR
  E1["1. Escrever
a recorrência"] --> E2["2. Substituir
iterativamente"]
  E2 --> E3["3. Reconhecer
o padrão"]
  E3 --> E4["4. Usar a
condição inicial"]
  E4 --> E5["5. Verificar
por indução"]
  E5 --> FEC(["fórmula fechada ✓"])

Resolvendo a Torre de Hanoi

#

Substituindo iterativamente:

Fórmula fechada: \(T_n = 2^n - 1\)

Verificação por indução:

Base (\(n=1\)): \(T_1 = 1 = 2^1 - 1\) ✓

HI: \(T_k = 2^k - 1\)

Passo (\(n = k+1\)):

Portanto, \(T_n = 2^n - 1\), que é o que queríamos demonstrar. \(\blacksquare\)

def hanoi(n, origem="A", destino="C", auxiliar="B"):
    if n == 1:
        print(f"Mover disco 1: {origem} → {destino}")
        return 1
    total  = hanoi(n - 1, origem, auxiliar, destino)
    print(f"Mover disco {n}: {origem} → {destino}")
    total += 1 + hanoi(n - 1, auxiliar, destino, origem)
    return total

print(hanoi(3))  # imprime os 7 movimentos e retorna 7

Exemplo: Ovais no Plano

#

São dados \(n\) ovais no plano obedecendo duas condições:

1. Quaisquer dois ovais se cruzam em exatamente 2 pontos distintos
2. Nenhum ponto pertence a três ou mais ovais simultaneamente (sem ponto triplo)

Em quantas regiões esses \(n\) ovais dividem o plano?

A figura abaixo mostra os casos \(n = 1, 2, 3\) com as regiões numeradas e os pontos de interseção marcados (pontos coloridos = interseções entre os pares de ovais):

Observando os casos concretos:

Por que cada nova oval acrescenta exatamente \(2(k-1)\) regiões?

Quando a \(k\)-ésima oval entra no plano, ela cruza cada uma das \(k-1\) ovais anteriores em exatamente 2 pontos — criando \(2(k-1)\) pontos de interseção sobre ela. Esses pontos dividem a borda da nova oval em \(2(k-1)\) trechos de curva (chamados de arcos) — cada um deles é o segmento da borda entre dois pontos de interseção consecutivos.

A chave é que cada arco fica inteiramente dentro de uma única região já existente (pois as fronteiras já existentes são cruzadas apenas nos pontos de interseção). Ao atravessar essa região, o arco a divide em duas, criando exatamente 1 nova região por arco.

Exemplo concreto (\(k = 3\), oval laranja no painel \(n=3\)): A oval laranja cruza a oval azul em 2 pontos (pontos verdes) e a oval magenta em 2 pontos (pontos violetas) — 4 pontos no total, que dividem a borda da laranja em 4 arcos. Cada arco corta uma das 4 regiões existentes ao meio: \(4 + 4 = 8\) regiões. ✓

Seja \(a_k\) o número de regiões com \(k\) ovais:

Resolvendo por substituição:

Fórmula fechada: \(a_n = n^2 - n + 2\)

Verificando: \(a_1 = 1 - 1 + 2 = 2\) ✓, \(a_2 = 4 - 2 + 2 = 4\) ✓, \(a_3 = 9 - 3 + 2 = 8\) ✓, \(a_4 = 16 - 4 + 2 = 14\) ✓

Indo além: recorrências de ordem 2

#

O método de substituição resolve recorrências onde cada termo depende apenas do anterior. Para recorrências lineares homogêneas de ordem 2 — onde cada termo é combinação linear dos dois anteriores, sem termos independentes — existe uma técnica sistemática chamada equação característica: supomos que a solução tem a forma \(a_n = r^n\) e descobrimos quais valores de \(r\) satisfazem a recorrência. O pipeline abaixo resume o fluxo completo para o caso de raízes distintas (\(\Delta \neq 0\)):

flowchart LR
  R["recorrência linear
homogênea de ordem 2"] --> S["supor
aₙ = rⁿ"]
  S --> Q["equação
característica"]
  Q --> Ro["raízes distintas
r₁ ≠ r₂"]
  Ro --> G["solução geral
A·r₁ⁿ + B·r₂ⁿ"]
  G --> CI["condições
iniciais"]
  CI --> FC(["fórmula fechada ✓"])

Para raízes repetidas (\(\Delta = 0\)), a forma correta é \((A + Bn) \cdot r^n\); esse caso não ocorre nos exemplos deste artigo.

Fibonacci

#

A recorrência \(F_n = F_{n-1} + F_{n-2}\) com \(F_1 = F_2 = 1\).

Substituindo \(F_n = r^n\) na recorrência:

Dividindo ambos os lados por \(r^{n-2}\) (com \(r \neq 0\)):

Pela fórmula quadrática:

As duas raízes são \(\varphi = \dfrac{1+\sqrt{5}}{2} \approx 1{,}618\) (razão áurea) e \(\psi = \dfrac{1-\sqrt{5}}{2} \approx {-0{,}618}\). Como as duas são soluções independentes, a solução geral é qualquer combinação linear delas:

Usando \(F_1 = 1\) e \(F_2 = 1\) para determinar \(A\) e \(B\):

Passo 1 — subtrair as equações das condições iniciais:

Como \(\varphi^2 - \varphi = \varphi(\varphi - 1) = 1\) e \(\psi^2 - \psi = 1\) (ambas raízes satisfazem \(r^2 = r+1\)), isso dá \(A + B = 0\), logo \(B = -A\).

Passo 2 — substituir \(B = -A\) em \(F_1 = 1\):

Obtemos a fórmula de Binet:

O artigo anterior da série demonstra essa fórmula por indução forte.

Expressões Aritméticas

#

A recorrência \(N_k = 10N_{k-1} + 40N_{k-2}\) com \(N_0 = 0\) e \(N_1 = 10\).

Substituindo \(N_k = r^k\) e dividindo por \(r^{k-2}\):

A solução geral é \(N_k = A(5+\sqrt{65})^k + B(5-\sqrt{65})^k\). Usando as condições iniciais:

• \(N_0 = 0 \implies A + B = 0 \implies B = -A\)
• \(N_1 = 10 \implies A \cdot 2\sqrt{65} = 10 \implies A = \dfrac{\sqrt{65}}{13}\)

Fórmula fechada:

Verificando contra a tabela:

• \(N_1 = \dfrac{\sqrt{65}}{13} \cdot 2\sqrt{65} = \dfrac{130}{13} = 10\) ✓
• \(N_2 = \dfrac{\sqrt{65}}{13} \cdot 20\sqrt{65} = \dfrac{1300}{13} = 100\) ✓

O contraste com o Fibonacci é instrutivo: a mesma técnica produz resultados de elegâncias muito diferentes. Fórmulas fechadas existem sempre para recorrências lineares — mas nem sempre são bonitas.

Tabela-Resumo

#

Os resultados provados neste artigo, reunidos para consulta rápida:

Exercícios

#

Pratique montando e resolvendo recorrências pelo método de substituição. Os exercícios 1 e 2 seguem o modelo dos exemplos vistos; os exercícios 3 e 4 exigem mais atenção à montagem da recorrência e à verificação algébrica.

Próximos passos

#

Com indução (simples e forte) e relações de recorrência no repertório, você tem as ferramentas fundamentais para raciocinar sobre estruturas definidas recursivamente. O próximo passo é a combinatória — a matemática da contagem. A próxima série, A Arte de Contar, usa esses fundamentos para construir a teoria das permutações, arranjos, combinações e o Binômio de Newton.