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 n 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 n, a fórmula que dá o número máximo de regiões criado por n retas em posição geral.
  • Vamos provar que o número de regiões é exatamente
1+\frac{n(n+1)}{2}.

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 n (normalmente n=0 ou n=1).
  • Passo indutivo: assumir que a afirmação é verdadeira para um n-1 arbitrário (hipótese de indução) e então mostrar que, sob essa hipótese, ela é verdadeira para n.
Se essas duas etapas são feitas corretamente, a afirmação vale para todo n natural.

Passo 3

Base da indução. Verificar a fórmula para alguns n pequenos para termos segurança.
  • Para n=0 (nenhuma reta) o plano tem exatamente uma região (toda a plana): a fórmula dá
1+\frac{0(0+1)}{2}=1,
logo correta.
  • Para n=1 (uma reta) o plano é dividido em duas regiões: a fórmula dá
1+\frac{1(1+1)}{2}=1+\frac{2}{2}=2,
logo correta.
Podemos aceitar a base n=0 (ou n=1); ambas verificadas. A partir daqui vamos provar o passo indutivo.

Passo 4

Enunciado da hipótese de indução. Suponha que para algum k\ge1 (ou k\ge0 se preferir) a afirmação seja verdadeira, isto é, suponha que k retas em posição geral dividem o plano em
1+\frac{k(k+1)}{2}
regiões. Esta é a nossa hipótese de indução. A meta é provar que k+1 retas em posição geral dividem o plano em
1+\frac{(k+1)(k+2)}{2}.

Passo 5

Construção do passo indutivo: partir de uma configuração com k retas e adicionar a (k+1)-ésima reta.
  • Tome uma configuração de k retas em posição geral, que por hipótese divide o plano em 1+\dfrac{k(k+1)}{2} regiões.
  • Agora desenhe uma nova reta r de modo que ela mantenha posição geral com as outras: isto é, r não seja paralela a nenhuma das k retas existentes e não passe por nenhum ponto onde duas já se intersectam (isso é possível, basta escolher r adequadamente).
  • Pelo fato de não haver paralelismo, r intersecta cada uma das k 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 r tem exatamente k pontos de interseção com as retas existentes. Esses k pontos dividem a reta r em exatamente k+1 segmentos (contando segmentos semi-infinitos nas extremidades ou, dito de outra forma, k+1 trechos contíguos ao longo de r).

Passo 6

Explicar por que cada um desses k+1 segmentos aumenta o número de regiões em exatamente 1.
  • Cada segmento de r fica contido em uma região distinta do arranjo das k retas (não podem ficar dois segmentos distintos de r na mesma região porque, entre dois segmentos consecutivos de r, existe um ponto de interseção com uma das retas antigas e isso separa as regiões).
  • Quando colocamos a reta r, 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 k+1 segmentos aumenta o número de regiões em 1.
Conclusão desta etapa: ao adicionar a (k+1)-ésima reta o número total de regiões aumenta em k+1.

Passo 7

Montar a relação de recorrência e concluir usando a hipótese de indução.
  • Sejam R(k) o número de regiões gerado por k retas em posição geral. Pelos argumentos anteriores temos a relação
R(k+1)=R(k)+(k+1).
  • Pela hipótese de indução R(k)=1+\dfrac{k(k+1)}{2}. Substituindo:
R(k+1)=1+\frac{k(k+1)}{2}+(k+1).
  • Colocar em comum factor k+1:
R(k+1)=1+\frac{k(k+1)+2(k+1)}{2}=1+\frac{(k+1)(k+2)}{2}.
  • Isso é exatamente a fórmula pretendida para k+1. Assim o passo indutivo está completo.

Passo 8

Fechamento e pequena explicação do somatório que aparece.
  • A recorrência R(n)=R(n-1)+n com R(0)=1 dá, somando termos,
R(n)=1+\sum_{j=1}^{n} j.
  • A soma dos primeiros n inteiros positivos é a conhecida fórmula dos números triangulares:
\sum_{j=1}^{n} j=\frac{n(n+1)}{2}.
Uma maneira rápida de ver isso é parear termos 1+n,\;2+(n-1),\;\dots obtendo n pares que somam n+1, e depois dividir por 2.
  • Portanto
R(n)=1+\frac{n(n+1)}{2}.

Resposta

1+\frac{n(n+1)}{2}

Exercícios relacionados