Princípio da indução finita

Definição e exemplos do princípio da indução finita

Este princípio é utilizado para a solução de diversos exercícios, porém ele serve apenas para aqueles que envolvem números inteiros e para exercícios que pedem que seja provado que algo é verdadeiro para um conjunto de valores inteiros.

Vou falar sobre o princípio utilizando a fórmula da soma da PA (Progressão Aritmética) para esclarecer.

 

Para isso, será necessário o uso da fórmula do termo geral da PA:

Voltamos ao método, que basicamente consiste em 3 etapas:

1ª Etapa - Dado um conjunto de valores inteiros que se deseja verificar a validade de algo proposto, deve-se verificar se é válido para o menor valor do conjunto.

No exemplo então, vamos verificar se a fórmula da soma da PA é válida para n = 1. Neste caso, é muito fácil perceber já que a soma será igual a a1, já que este é o único termo.

Vamos verificar se usando a fórmula o resultado é obtido:

O resultado obtido é correto, logo a fórmula da Soma da PA vale para o menor elemento do conjunto.

2ª Etapa - Assume-se que para um elemento 'k' qualquer e genérico do conjunto a fórmula é verdadeira.

Do exemplo vamos calcular a soma dos primeiros 'k' elementos do conjunto, neste caso, pela fórmula da soma da PA teremos que:

3ª Etapa - Assumindo que o resultado obtido na Etapa 2 seja verdadeiro, calculamos o resultado para 'k+1' e verificamos se obtemos a fórmula desejada.

Do exemplo usado temos então que a soma dos 'k+1' primeiros elementos é a soma dos 'k' primeiros elementos mais o elemento 'k+1'. Veja:

Observe que se usarmos a fórmula da soma da PA para calcular a soma dos 'k+1' primeiros termos (substituindo n = k+1) teremos exatamente o resultado acima. Portanto, provamos que a fórmula é válida sempre. Porém, por que podemos concluir isso? Por que o uso do princípio garante a validade da fórmula para qualquer quantidade de elementos?

Bom, tudo se resume às etapas que foram seguidas. 

Foi mostrado que para o primeiro elemento a fórmula é válida. 

Após isso, supomos na Etapa 2 que para um número de elementos 'k' qualquer ela é válida e a partir do resultado da Etapa 2 obtemos o resultado para 'k+1' e verificamos que ele é válido. A grande dúvida que surge é por que podemos garantir que o resultado obtido na Etapa 2 é válido?

Na verdade a gente não garante isso, apenas supõe. Porém se a partir do resultado da Etapa 2 pudermos obter um resultado satisfatório na Etapa 3 então o resultado é válido. O que garante isso é o seguinte raciocínio:

- Para o menor elemento a equação é válida;

- Então, se 'k' = 1 a nossa suposição da Etapa 2 é verdadeira, e não apenas uma suposição, já que mostramos na Etapa 1 isso;

- Mas na Etapa 3 nós mostramos que se 'k' é verdadeiro, então 'k+1' também é;

- Como para 'k' = 1 vimos que é verdadeiro na Etapa 1, então certamente para 'k+1' = 2 também será, como visto na Etapa 3;

- Mas se para 'k' = 2 é verdadeiro, então para 'k+1' = 3 também será;

- Mas se para 'k' = 3 é verdadeiro, então para 'k+1' = 4 também será;

- ...

Assim, o princípio garante que para qualquer 'k' ele é verdadeiro, desde que as etapas sejam satisfeitas.

Exercícios que o princípio foi usado:

Somatório de n²

Dedução da fórmula da soma da PG por indução

Aula sobre PG

Exercício Resolvido - Limite e função

Seja o conjunto de funções do tipo fn(x) = -(1/kn²)x + 2/kn, onde kn assume qualquer valor real positivo. Determine qual é a função g(x) formada pela intersecção de infinitas retas do tipo fn, conforme figura a seguir.

Solução:
Veja que na figura acima as retas do gráfico foram para os valores de k = n/3, para n = 1,2,3,...,12, conforme figura que segue:

Quando estas retas são sobrepostas é que é possível ver a tendência à formação de uma outra curva, neste caso ilustrada em preto na figura ilustrativa do exercício. Porém, é importante perceber que não é simplesmente a intersecção das retas que gera esta curva, mas sim a intersecção das retas mais próximas, ou seja, a intersecção da reta para k = 1/3 com a reta para k = 4 não fica na fronteira formadora da curva desejada. Além disso, a formação da curva acontece à medida que os valores de k se aproximam. Perceba na figura abaixo que, na verdade, a curva g(x) não passa pelos pontos de intersecção das retas, mas a medida que os valores de k se tornam mais próximos, o ponto de intersecção passa a se aproximar de g(x).

Neste caso, as retas foram formadas para k1 = 2 e k2 = 2/3.

Para k1 = 0,95 e k2 = 1,05 foi preciso dar um zoom na figura para poder ver exatamente o que acontece, pois o ponto de intersecção das retas se aproxima muito da curva em preto:

Veja que o ponto esta mais próximo, mas a curva g(x) ainda não passa por ele. Na verdade o ponto de intersecção das retas será um ponto da curva g(x) apenas no limite para k1 tendendo a k2.

Neste caso então, vou supor que k2 = k1 + eps, onde 'eps' é um valor muito pequeno, depois irei fazer ele tender a zero. Assim, substituindo na equação fn(x) temos:

Mas no ponto de intersecção, f1(x) = f2(x)

Assim, calculamos o valor de x no ponto de intersecção. Chamarei de xo:

Fazendo o limite para eps tendendo a zero, temos:

Substituindo na equação f1 para x = xo = k1 temos:

Obs.: Se xo = k1 fosse substituído na função f2, para k2 = k1 + eps com eps tendendo a zero, o resultado seria o mesmo, já que estamos procurando o ponto de intersecção.

Assim, temos que no limite, para k1 tendendo a k2 (ou seja, para eps tendendo a zero) o ponto de intersecção das curvas é dado pelo par ordenado (k1, 1/k1). Ou seja, y = 1/x. Logo, a função g(x) definida pelas retas é:

g(x) = 1/x

Veja a seguir o gráfico com 100 curvas e, no gráfico da direita em preto, a curva g(x) = 1/x

Exercício Resolvido - Inteiros de Gauss

O exercício resolvido neste post será o Problema 1 do capítulo "Inteiros de Gauss" do arquivo disponível no link http://www.obm.org.br/export/sites/default/revista_eureka/docs/artigos/gauss.doc escrito por Guilherme Fujiwara.
Deste arquivo irei transcrever algumas definições e teoremas, conforme eles forem sendo usados, porém não serão disponibilizadas aqui as provas dos teoremas. Estas podem ser vistas no próprio documento.

Problema 1. Determine todos os pares x, y Î Z tal que y³ = x² + 1.

Solução:

y³ = x² + 1

y³ = (x + i)*(x - i)

onde

i² = -1.

INTEIROS DE GAUSS
Definimos o conjunto Z[i] dos inteiros de Gauss como Z[i] = {a + bi | a, b Є Z}, onde (i² = –1).

Fatoração única

Todo inteiro z de Gauss com norma maior que 1 pode ser escrito como o produto de um ou mais primos de Gauss. Além disso, esta fatoração é única.

Desta forma, como desejamos soluções pertencentes a Z para x e y, então (x + i) e (x - i) são inteiros de Gauss. Portanto, pela propriedade da fatoração única, cada um deles pode ser escrito como o produto de primos de Gauss, onde um primo de Gauss é definido por ser um inteiro de Gauss que não pode ser escrito pelo produto de dois inteiros de Gauss não unitários.

Assim:

(x + i) = (α1)ᵃ¹*(α2)ᵃ²*(α3)ᵃ³*...*(αk1)ᵃᵏ¹

(x - i) = (β1)ᵇ¹*(β2)ᵇ²*(β3)ᵇ³*...*(βk2)ᵇᵏ²

onde αn e βn são primos de Gauss e an e bn são os expoentes dos termos da fatoração.

Da fatoração acima, será necessário saber se existe algum α ou β iguais, ou seja, se algum dos primos da fatoração de (x + i) é igual a algum dos primos da fatoração de (x - i). O que se pode deduzir é que, se existe algum termo das fatorações de ambos que sejam iguais, então este primo também é um termo na fatoração de qualquer combinação aritmética (soma, subtração, divisão e multiplicação) entre eles.
Fazendo:
(x + i) - (x - i) = 2i
(x + i) + (x - i) = 2x
Portanto, caso exista algum α que seja igual a algum β, este é 2 (ou 2i, ou -2, ou -2i), já que as unidades dos inteiros de Gauss são 1, -1, i e -i.

Obs.: É importante perceber que o 2 não é, necessariamente, um termo da fatoração. O que se ressalta aqui é que se o 2 for termo da fatoração de um deles, então é dos dois e neste caso este seria o único termo em comum na fatoração de (x + i) e (x - i). Logo, qualquer α é diferente de qualquer β, exceto se um deles for 2.

Porém, da divisibilidade temos que:

Divisibilidade
Dizemos que para a, b Є Z[i], a|b (lê-se a divide b) se Ǝ c Є Z[i] tal que b = ac.

Logo, se 2ᵏ é fator da decomposição de (x + i), então existe um c = (a + bi) (inteiro de Gauss) tal que:

x + i = 2ᵏ*(a + bi)

x + i = 2ᵏ*a + 2ᵏ*bi

Ou seja:

2ᵏ*b = 1. Mas como b é um inteiro, então k = 0.

Portanto, a equação inicial fica:
y³ = [(α1)ᵃ¹*(α2)ᵃ²*(α3)ᵃ³*...*(αk1)ᵃᵏ¹]*[(β1)ᵇ¹*(β2)ᵇ²*(β3)ᵇ³*...*(βk2)ᵇᵏ²]

Porém, para que y seja inteiro, cada um dos expoentes a1, a2, a3, ..., ak1 e b1, b2, b3, ..., bk2 devem ser múltiplos de 3, já que todos os primos de Gauss α e β são diferentes. Desta forma podemos escrever a equação:
y³ = [(α1)ᵃ¹'*(α2)ᵃ²'*(α3)ᵃ³'*...*(αk1)ᵃᵏ¹'*(β1)ᵇ¹'*(β2)ᵇ²'*(β3)ᵇ³'*...*(βk2)ᵇᵏ²']³
Além disso:
(x + i) =  [(α1)ᵃ¹'*(α2)ᵃ²'*(α3)ᵃ³'*...*(αk1)ᵃᵏ¹']³
e
(x - i) = [(β1)ᵇ¹'*(β2)ᵇ²'*(β3)ᵇ³'*...*(βk2)ᵇᵏ²']³
Usando:
(α1)ᵃ¹'*(α2)ᵃ²'*(α3)ᵃ³'*...*(αk1)ᵃᵏ¹' = u + vi
Onde u + vi é um inteiro de Gauss.

Assim:
(x + i) = (u + vi)³ = [u³ + 3u²vi + 3u(vi)² + (vi)³] = u³ + 3u²vi - 3uv² - v³i = (u³ - 3uv²) + i*(3u²v - v³)
Então:
(x + i) = (u³ - 3uv²) + i*(3u²v - v³)
e
(x - i) = (u³ - 3uv²) - i*(3u²v - v³)
Logo:
3u²v - v³ = 1
3u² - v² = 1/v

Porém, como u é um inteiro e v também é um inteiro, v só pode ser ±1, caso contrário |1/v| < 1, o que não é uma solução possível para 3u² - v² sendo u e v inteiros.

Assim:
Para v = 1:
3u² - 1 = 1
u² = 3/2
O que não é possível, pois u é inteiro.

Para v = -1
3u² - 1 = -1
u = 0
Ok.

Logo:
(x + i) = (u³ - 3uv²) + i*(3u²v - v³) = 0 + i
Ou seja
x = 0

Neste caso
y³ = 0² + 1
y = 1

Portanto, este exercício só admite uma solução:
x = 0
y = 1