Exemplos – Indução Matemática
Exemplo
Considere o seguinte trecho de código.
Prog1(int k)
Se k=1
Print(’OI’)
Return
Senão
Para i = 1, . . . , k
Print(’OI’)
Fim Para
Prog1(k-1)
Fim Se
Seja T (n) o número de vezes que a palavra “OI” é impressa quando
Prog1 é chamado com parâmetro n.
Prova por indução que T (n) = k (k + 1)/2.
>
1/9
Exemplos – Indução Matemática
Exemplo
Prove que a soma dos ângulos de um polı́gono convexo de n vértices é
180(n − 2) para todo n ≥ 3.
>
2/9
Exemplos – Indução Matemática
Prova:
Base: n = 3, já que n = 1 ou n = 2 não fazem sentido.
Nesse caso a figura é um triângulo e supomos já conhecido o teorema
que demonstra que a soma dos ângulos internos de um triângulo é
180 graus.
>
3/9
Exemplos – Indução Matemática
Hipótese Indutiva:
A soma dos ângulos internos de um polı́gono com k lados é 180.(k − 2)
Passo Indutivo
Provar a propriedade para k + 1, ou seja, a soma vale 180(k − 1)
graus.
>
4/9
Exemplos – Indução Matemática
Prova do Passo:
Considere um polı́gono de k + 1 vértices V1 ,V2 ,...,Vk +1 . Podemos
traçar um segmento de reta unido os vértices V1 a Vk . Desta forma,
obtemos um triângulo V1 Vk Vk +1 e um polı́gono de k vértices.
Sabemos pela hipótese de indução que a soma dos ângulos de um
polı́gono de k vértices é 180(k − 2) graus. Logo a soma dos ângulos
de um polı́gono com k + 1 vértices é
180(k − 2) + 180 = 180(k − 1)
>
5/9
Exemplos – Indução Matemática
Exemplo
Retas no plano: Um conjunto de n retas no plano estão em posição
geral se e somente se não existem duas retas paralelas nem três retas
se interceptando no mesmo ponto. Mostre que n retas em posição
+ 1 regiões
geral dividem o plano em n(n+1)
2
>
6/9
Exemplos – Indução Matemática
Prova:
Base. Para n = 1 a fórmula é válida.
Passo Indutivo. Se Rk =
para k ≥ 1.
k (k +1)
2
+ 1 então Rk +1 =
(k +1)(k +2)
2
+ 1,
Prova do Passo: Suponha um conjunto de k retas em posição geral.
A reta k + 1 interceptará cada uma das k retas em um ponto distinto.
Portanto k + 1 segmentos de retas são criados. Cada um dos
segmentos divide a região que o contém em duas novas regiões.
Portanto, temos:
Rk +1 = Rk + k + 1
Como Rk = k (k2+1) + 1 (hipótese indutiva), segue que:
+2)
Rk +1 = k (k2+1) + 1 + k + 1 = (k +1)(k
+1
2
>
7/9
Exemplos – Indução Matemática
Prove o Teorema seguinte:
Teorema
Ao final de qualquer campeonato em que todos os n participantes
jogaram entre si, é possı́vel, independentemente dos resultados,
classificar os participantes de forma que, para todo
i ∈ {1, 2, . . . , n − 1}, pi vence pi+1
>
8/9
Exemplos – Indução Matemática
Prove o Teorema seguinte:
Teorema
Qualquer quantia Q superior a 7 centavos pode ser paga exatamente
apenas com moedas de 3 centavos e 5 centavos.
>
9/9