Seja
o número de regiões ilimitadas em que um plano é dividido por
retas tais que a interseção de qualquer subconjunto de
retas
só é diferente de vazio para
. Monte e resolva uma relação de recorrência para
.
Passo 1
O enunciado define
como o número de regiões ilimitadas em que o plano é dividido por
retas, sob a condição de que a interseção de qualquer subconjunto de
retas (
) só é diferente de vazio para
. Ou seja:
- Cada par de retas se intersecta em um ponto distinto.
- Não há retas paralelas e não há três (ou mais) retas concorrentes no mesmo ponto.
O que o problema pede:
- Montar uma relação de recorrência que determine
. - Resolver essa relação (obter a fórmula fechada para
).
Informações relevantes dadas:
- Para
retas em posição geral (sem paralelas e sem três concorrentes), cada nova reta intersecta todas as anteriores em pontos distintos; a -ésima reta tem exatamente pontos de interseção com as anteriores.
Passo 2
Ideia de resolução (estratégia): construir as retas uma a uma e analisar quanto a quantidade de regiões ilimitadas aumenta quando acrescentamos a reta
. Esse é um método padrão de recorrência por adição incremental: comparar a configuração com
retas e com
retas e contar quantas regiões ilimitadas surgem ao inserir a nova reta.
Antes de contar, vamos definir claramente “região ilimitada”: é uma região do plano que não é limitada — isto é, que se estende até o infinito. Visualmente, é uma região que tem pelo menos um “ramo” que vai ao infinito.
Passo 3
Casos iniciais (base):
- Para
(nenhuma reta), o plano inteiro é uma única região ilimitada. Logo
- Para
(uma reta), a reta divide o plano em duas metades, ambas ilimitadas. Logo
Esses casos servem para fixar condições iniciais da recorrência.
Passo 4
Contagem do acréscimo ao inserir a reta
(para
) — argumento detalhado e didático:
Quando adicionamos a
-ésima reta, ela intersecta cada uma das
retas já existentes em pontos distintos (pela hipótese do enunciado). Esses
pontos dividem a nova reta em
segmentos consecutivos ao longo dela: há
segmentos internos (entre dois pontos de interseção) e 2 semirretas externas (uma de cada extremidade), que são infinitas.
-
Cada um dos
segmentos internos fica “entre” duas interseções; esses segmentos ficam contidos em regiões que são limitadas pelo arranjo das retas, portanto, quando a reta corta essas regiões ela as subdivide, criando regiões novas que normalmente são limitadas. Assim, esses cortes internos não aumentam o número de regiões ilimitadas do plano. -
As 2 semirretas externas da
-ésima reta (as duas extremidades que vão até o infinito) entram em regiões que tocavam o infinito e as dividem em duas cada uma. Cada semirreta externa, ao atravessar uma região ilimitada já existente, cria exatamente mais uma região ilimitada. Logo as duas extremidades juntas acrescentam exatamente 2 regiões ilimitadas.
Portanto, ao inserir a
-ésima reta (para
) o número de regiões ilimitadas aumenta em
.
Passo 5
Escrevendo a recorrência e resolvendo-a:
A partir da observação do passo anterior, para
vale a recorrência
Como condição inicial usamos
.
Resolver essa recorrência é simples: é uma progressão aritmética com razão
. Podemos escrever a solução fechada somando
repetidas vezes:
para todo
.
Podemos também provar por indução que
para
:
- Base: para
, . - Passo indutivo: suponha
. Então pela recorrência
Logo vale para
. Assim, por indução,
para todo
.
Observação final: mantemos
como caso especial (a fórmula
não vale para
).
Resposta
Relação de recorrência:
para
, com condição inicial
.
Solução fechada:
para
.
Além disso, .\
Além disso,