Seção 3.1
Seja x_{n} o número máximo de regiões em que n retas podem dividiro plano. Caracterize x_{n} recursivamente.

Passo 1

O enunciado define x_{n} como o número máximo de regiões em que n retas podem dividir o plano e pede uma caracterização recursiva de x_{n}.
Informações dadas e o que se pede:
  • Dado: para cada inteiro n\ge 0, x_{n} é o máximo de regiões obtidas com n retas.
  • Pedido: encontrar uma relação recursiva que determine x_{n} a partir de valores anteriores (ou seja, expressar x_{n} em função de x_{n-1} ou de termos anteriores) e o caso inicial necessário.

Passo 2

Para maximizar o número de regiões, devemos colocar as retas em posição “geral”, isto é: nenhuma duas retas sejam paralelas e não haja três retas concorrendo num mesmo ponto. Explique por que isso importa: se houver retas paralelas ou três (ou mais) passando pelo mesmo ponto, elas criam menos interseções e, portanto, menos segmentos e menos regiões. Então, ao buscar o valor máximo x_{n}, assumimos que as n retas estão em posição geral.

Passo 3

Considere que já temos uma configuração ótima com n-1 retas, que produz x_{n-1} regiões (isso é a hipótese recursiva). Agora adicionamos a n-ésima reta. Cada uma das n-1 retas anteriores pode intersectar a nova reta em no máximo um ponto, e como não permitimos três retas concorrendo, essas interseções são todas distintas. Logo o número máximo de pontos de interseção da nova reta com as anteriores é n-1.

Passo 4

Esses n-1 pontos de interseção dividem a nova reta em n pedaços (segmentos), porque um segmento aparece entre dois pontos consecutivos de interseção, e há ainda dois semi-intervalos infinitos nas pontas; em termos gerais, número de segmentos = número de interseções +1. Ou seja, a nova reta fica dividida em exatamente n partes.

Passo 5

Cada um desses n segmentos corta uma região já existente em duas, aumentando o número total de regiões em 1 para cada segmento. Explicação geométrica simples: entre duas interseções consecutivas a porção da reta está inteiramente dentro de uma região única e a traça dessa porção divide essa região em duas. Não há sobreposição de efeitos porque assumimos posição geral (sem interseções múltiplas). Portanto, ao inserir a n-ésima reta, o número de regiões aumenta em n.

Passo 6

Da observação anterior segue a relação recursiva para n\ge 1:
x_{n}=x_{n-1}+n.
Precisamos também do caso inicial: com zero retas o plano fica inteiro, ou seja,
x_{0}=1.
Como checagem rápida, para n=1 obtemos x_{1}=x_{0}+1=2, que faz sentido (uma reta divide o plano em duas regiões).

Passo 7

Opcional: resolução fechada da recorrência (útil na prova). Somando a recorrência desde k=1 até k=n obtemos
x_{n}=x_{0}+\sum_{k=1}^{n}k.
Usando a fórmula da soma dos primeiros n inteiros \sum_{k=1}^{n}k=\dfrac{n(n+1)}{2} (pode ser provada por emparelhamento ou indução), obtemos a forma fechada
x_{n}=1+\frac{n(n+1)}{2}.
Verificação para valores pequenos: para n=0,1,2,3 temos respectivamente 1,2,4,7, que batem com desenhos mentais ou casos conhecidos.

Resposta

x_{n}=x_{n-1}+n,\quad x_{0}=1
x_{n}=1+\frac{n(n+1)}{2}

Exercícios relacionados