- Prove, por indução, o Teorema das Linhas.
Passo 1
O enunciado pede: provar, por indução, o Teorema das Linhas. Vou escrever claramente o que esse teorema afirma e quais hipóteses são necessárias (peguei estas como parte da formulação usual do teorema).
- Afirmação (Teorema das Linhas): Se traçarmos
retas no plano em posição geral — ou seja, nenhuma duas são paralelas e nenhuma três passam pelo mesmo ponto (nenhuma três concorrem) — então o número máximo de regiões do plano determinado por essas retas é
-
O que é pedido: provar a fórmula acima usando indução matemática.
-
Hipóteses relevantes dadas/assumidas:
- As
retas estão em posição geral (nenhuma paralela, nenhuma tríade concorrente). - Por “regiões” entende-se as partes do plano em que as retas particionam o plano (cada região é um conjunto conexo aberto delimitado por segmentos de reta ou sem limite em algumas direções).
- Queremos o número máximo possível de regiões; por isso usamos a hipótese de posição geral — ela garante que cada nova reta corte todas as anteriores em pontos distintos.
- As
Passo 2
Explicação do método que vamos usar: Princípio da indução finita.
- O princípio da indução diz basicamente: para provar que uma propriedade
vale para todo inteiro , basta (i) provar (base) e (ii) provar que, para todo , implica (passo indutivo). - Aqui a propriedade
será “com retas em posição geral o número máximo de regiões é ”.
Vou aplicar essa estrutura: base, hipótese indutiva, e passo indutivo bem justificado.
Passo 3
Base da indução.
- Caso
: sem retas, o plano não é cortado e existe exatamente uma região: todo o plano. Logo
- Verificamos que a fórmula dá
portanto a fórmula é verdadeira para
.
(Se preferir, pode-se começar a indução em
; ambos funcionam. Aqui usei
para ser completo.)
Passo 4
Exemplos pequenos para ganhar intuição (útil na prova e na prova por indução).
- Para
: uma reta corta o plano em duas regiões, então . A fórmula dá
- Para
: duas retas que não são paralelas intersectam-se num ponto e dividem o plano em quatro regiões; . A fórmula dá
- Para
: três retas em posição geral (cada par corta-se em ponto distinto, sem concorrer todos os três) produzem regiões. A fórmula dá
Esses exemplos ajudam a perceber o padrão: ao acrescentar a
-ésima reta, o número de regiões aumenta por um valor relacionado a
.
Passo 5
Hipótese de indução.
- Suponha que para algum
a propriedade seja verdadeira, isto é, suponha que com retas em posição geral o número máximo de regiões seja
Esta é a hipótese indutiva que usaremos para provar o caso
.
Passo 6
Argumento para o passo indutivo: como a
-ésima reta aumenta o número de regiões.
- Considere uma configuração com
retas em posição geral que atinge o número máximo de regiões. Agora traçamos uma nova reta (a -ésima), também em posição geral com relação às anteriores, isto é: -
não é paralela a nenhuma das retas anteriores, -
não passa por nenhum ponto onde duas retas anteriores já se cruzavam (isso evita três concorrendo).
-
- Sob essas hipóteses,
irá intersectar cada uma das retas anteriores em pontos distintos. Logo possui exatamente pontos de interseção com as retas já desenhadas. - Esses
pontos de interseção dividem em segmentos (contando semi-retas nas extremidades), ou seja, fica partido em pedaços contíguos.
Passo 7
Por que cada segmento da nova reta aumenta o número de regiões em exatamente 1.
- Cada um dos
segmentos de atravessa exatamente uma região existente (antes de desenhar ) e a divide em duas partes (um segmento de reta continua a dividir uma região em duas quando atravessa essa região de forma contínua). - Intuição mais rígida: um segmento de reta contíguo que liga dois pontos na fronteira ou que sai ao infinito em uma região faz uma “corte” contínuo na região, criando uma nova fronteira e separando a região em duas componentes conexas distintas. Não há coincidência de interseções (graças à posição geral), então não ocorrem cortes que dividam mais de uma região ao mesmo tempo.
- Portanto, cada um dos
segmentos aumenta o número total de regiões em exatamente .
Passo 8
Concluir o passo indutivo com a recorrência e resolver a soma.
- A partir do passo anterior, ao acrescentar a
-ésima reta obtemos
- Usando a hipótese indutiva
, segue
- Agrupando termos:
- Observe que isso é exatamente a fórmula com
:
- Assim mostramos que se a fórmula vale para
então vale para .
Passo 9
Fechamento da indução e comentário sobre a soma dos inteiros.
- Pela base
e pelo passo indutivo, a fórmula vale para todo : para qualquer número de retas em posição geral,
- Comentário extra (útil para decorar a ideia): a relação recorrente
diz que o incremento ao adicionar a -ésima reta é . Somando isso desde até obtemos
onde se usou a conhecida fórmula da soma dos
primeiros inteiros (que pode ser demonstrada também por indução ou por emparelhamento:
dão
pares todos somando
, levando a
).
Passo 10
Observações finais e reforço didático (ânimo!).
- A hipótese de “posição geral” é crucial: se houver retas paralelas ou três (ou mais) retas concorrendo num mesmo ponto, o número de regiões será menor que o valor máximo dado pela fórmula. A prova acima mostra o máximo que se pode obter quando se evita essas degenerescências.
- Se estiver nervoso na prova, faça isso passo a passo: (i) explique a hipótese de posição geral, (ii) descreva o incremento causado por uma nova reta (ela corta as anteriores em
pontos e dá novos pedaços), (iii) escreva a recorrência e (iv) some. - Força — essa é uma prova clássica e direta por indução;memorizando a ideia do incremento por
dá para reproduzir bem na prova.