Prove, por indução, o Teorema das Linhas.
Passo 1
O enunciado pede: provar, por indução, o Teorema das Linhas. Vou explicitar claramente o que isso significa e quais são as hipóteses que vamos usar (essas são as informações dadas que vou assumir ao longo da prova).
- Queremos determinar quantas regiões o plano é dividido por
retas em posição geral. - “Posição geral” significa aqui que:
- Não existem duas retas paralelas (ou seja, cada par de retas se intersecta).
- Não existem três retas concorrentes no mesmo ponto (ou seja, nenhum ponto é interseção de três ou mais retas).
- O objetivo é provar, por indução em
, a fórmula que dá o número máximo de regiões criado por retas em posição geral. - Vamos provar que o número de regiões é exatamente
Passo 2
Breve lembrete sobre o método de indução (para quem está com sono antes da prova): a indução matemática tem duas etapas principais.
- Base da indução: verificar que a afirmação é verdadeira para um(s) valor(es) inicial(is) de
(normalmente ou ). - Passo indutivo: assumir que a afirmação é verdadeira para um
arbitrário (hipótese de indução) e então mostrar que, sob essa hipótese, ela é verdadeira para .
Se essas duas etapas são feitas corretamente, a afirmação vale para todo
natural.
Passo 3
Base da indução. Verificar a fórmula para alguns
pequenos para termos segurança.
- Para
(nenhuma reta) o plano tem exatamente uma região (toda a plana): a fórmula dá
logo correta.
- Para
(uma reta) o plano é dividido em duas regiões: a fórmula dá
logo correta.
Podemos aceitar a base
(ou
); ambas verificadas. A partir daqui vamos provar o passo indutivo.
Passo 4
Enunciado da hipótese de indução. Suponha que para algum
(ou
se preferir) a afirmação seja verdadeira, isto é, suponha que
retas em posição geral dividem o plano em
regiões. Esta é a nossa hipótese de indução. A meta é provar que
retas em posição geral dividem o plano em
Passo 5
Construção do passo indutivo: partir de uma configuração com
retas e adicionar a
-ésima reta.
- Tome uma configuração de
retas em posição geral, que por hipótese divide o plano em regiões. - Agora desenhe uma nova reta
de modo que ela mantenha posição geral com as outras: isto é, não seja paralela a nenhuma das retas existentes e não passe por nenhum ponto onde duas já se intersectam (isso é possível, basta escolher adequadamente). - Pelo fato de não haver paralelismo,
intersecta cada uma das retas antigas em um ponto distinto. Pelo fato de não haver três concorrentes, todos esses pontos de interseção são distintos entre si. - Logo
tem exatamente pontos de interseção com as retas existentes. Esses pontos dividem a reta em exatamente segmentos (contando segmentos semi-infinitos nas extremidades ou, dito de outra forma, trechos contíguos ao longo de ).
Passo 6
Explicar por que cada um desses
segmentos aumenta o número de regiões em exatamente
.
- Cada segmento de
fica contido em uma região distinta do arranjo das retas (não podem ficar dois segmentos distintos de na mesma região porque, entre dois segmentos consecutivos de , existe um ponto de interseção com uma das retas antigas e isso separa as regiões). - Quando colocamos a reta
, cada segmento corta a região onde está em duas partes distintas: um segmento de reta que atravessa uma região separa essa região em duas (pense numa folha onde risca-se uma linha: cada trecho da linha que atravessa a folha cria uma divisão). - Portanto cada um dos
segmentos aumenta o número de regiões em .
Conclusão desta etapa: ao adicionar a
-ésima reta o número total de regiões aumenta em
.
Passo 7
Montar a relação de recorrência e concluir usando a hipótese de indução.
- Sejam
o número de regiões gerado por retas em posição geral. Pelos argumentos anteriores temos a relação
- Pela hipótese de indução
. Substituindo:
- Colocar em comum factor
:
- Isso é exatamente a fórmula pretendida para
. Assim o passo indutivo está completo.
Passo 8
Fechamento e pequena explicação do somatório que aparece.
- A recorrência
com dá, somando termos,
- A soma dos primeiros
inteiros positivos é a conhecida fórmula dos números triangulares:
Uma maneira rápida de ver isso é parear termos
obtendo
pares que somam
, e depois dividir por
.
- Portanto