Indução Matematica, Fundamentos

Prévia do material em texto

Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
Fundamentos matemáticos: Indução Matemática
Por que é importante a indução matemática?
Para prosseguirmos com a análise da eficiência dos algoritmos, baseando-nos em modelos
matemáticos, é primeiramente necessário que revisemos alguns conceitos sobre indução
matemática.
A indução matemática é parte da matemática aplicada, que é uma área da matemática que trata da
aplicação do conhecimento matemático a outros domínios como, por exemplo, a ciência da
computação. No projeto de algoritmos a indução matemática é muito útil para provar a correção
(corretude) e a eficiência dos algoritmos (Real, 2013).
A indução matemática é um método para provar a verdade de um número infinito de proposições
sobre números naturais. A forma mais simples consiste de dois passos:
1. Passo base: mostrar que a proposição é verdadeira para um valor inicial.
2. Passo indutivo: mostrar que se a proposição vale para n=k (hipótese indutiva), então também
vale para n=k+1. Logo, a proposição é verdadeira para todo o conjunto.
Em outras palavras, temos o axioma da indução (axioma da indução de Peano):
Suponha que 
 P(1) é verdadeira;
∀m∈N , P (m)→P (m+1)
Então
∀m∈N , P (n) é verdadeira
Axioma: “Premissa considerada necessariamente evidente e verdadeira, fundamento de uma
demonstração, porém ela mesma indemonstrável, originada, segundo a tradição racionalista, de
princípios inatos da consciência ou, segundo os empiristas, de generalizações da observação
empírica [O princípio aristotélico da contradição ('nada pode ser e não ser simultaneamente') foi
considerado desde a Antiguidade um axioma fundamental da filosofia.]”.
Em contraste aos teoremas, axiomas não podem ser derivados por princípios de dedução e
demonstráveis por derivações formais, eles são hipóteses iniciais.
Segundo Real (2013) a prova de um teorema por meio da indução matemática, pode seguir (ou
conter) as seguintes partes:
(i) Base ou bases.
(ii) Hipótese de indução T(α).
(iii) Redução de T(β) para T(α).
(iv) Prova de que T(α) implica em T(β).
Não importa a ordem e as partes devem formar um todo consistente.
Segundo Hefez (2007), a indução matemática é diferente da indução empírica das ciências naturais,
em que é comum, depois de um certo número de experimentos, enunciar leis gerais que são
verdades até que se prove o contrário. Na matemática não acontece isso. A prova por indução
matemática estabelece que uma sentença sobre os naturais é sempre verdadeira. 
1
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
Exemplo 1 
(Hefez, 2007)
Determinar a fórmula para a soma dos n primeiros números naturais.
Há uma história que envolve o matemático alemão Carl Friedrich Gauss (1777-1855) quando ainda
garoto. Na escola, o professor, para aquietar a turma, pediu para que eles calculassem a soma de
todos os números naturais de 1 a 100. Não demorou muito para que Gauss desse a resposta: 5050.
Surpreso, o professor indagou como ele tinha descoberto tão rápido o resultado. Gauss, aos seus 9
anos de idade, descreveu o método a seguir:
Sendo 
Sn = 1 + 2 + 3 + … + n,
o objetivo é encontrar uma fórmula fechada1 para Sn. 
Somando a igualdade anterior termo a termo com ela mesma, porém com os elementos do segundo
membro em ordem invertida, temos que:
Sn = 1 + 2 + 3 + … + n
Sn = n + (n-1) + (n-2) + … + 1
2Sn= (n+1) + (n+1) + (n+1) + … + (n+1)
Segue que 2Sn = n (n+1) e, portanto, 
S n=
n(n+1)
2
 
Entretanto, essa demonstração não é válida para afirmar a veracidade do método. Para tal, vamos
provar a fórmula pela indução matemática:
Queremos provar P (n) :1+2+...+n=n (n+1)
2
Passo base:
Para n=1 temos: 
P (1) : 1(1+1)
2
=1 é verdadeira
Passo indutivo:
Deve-se demonstrar que:
P (n+1) :1+2+...+n+(n+1)=(n+1)(n+1+1)
2
=
(n+1)(n+2)
2
Hipótese indutiva: Considerando P (n) :1+2+...+n=n (n+1)
2
verdadeira, somando (n+1) em
ambos os lados da igualdade temos:
1 fórmula fechada é, a grosso modo, uma fórmula composta por polinômios, quocientes de polinômios, logaritmos,
exponenciais, etc. em que se pode calcular diretamente os valores do objeto em estudo fazendo um número pequeno
de contas.
2
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
1+2+...+n+(n+1)= n(n+1)
2
+(n+1)
=
n(n+1)+2(n+1)
2
=n
2+3 n+2
2
=
(n+1)(n+2)
2
(fatoração de polinômios)
Também podemos verificar que 
P(n+1) = 1 + 2 + … + n + (n+1)
P(n+1) = P(n)+ (n+1)
P (n+1)=n(n+1)
2
+(n+1)
O que estabelece a veracidade para P(n+1).
Exemplo 2
Prove que P(n) = 20 + 21 + 22 + 23 + … + 2n = 2n+1 – 1 para todo n ≥ 1.
Passo base: 
Para n ≥ 1, ou seja, P(1), temos:
20 + 21 = 21+1 – 1
1 + 2 = 21+1 – 1
3 = 22 – 1
3 = 3
Então P(1) é verdadeira.
Passo indutivo:
Temos que provar P(n+1) = 20 + 21 + 22 + 23 + … + 2n + 2n+1 = 2(n+1)+1 – 1
Hipótese indutiva: Considerando P(n) = 20 + 21 + 22 + 23 + … + 2n = 2n+1 – 1 para n ≥ 1 verdadeira.
Sendo P(n+1) = 20 + 21 + 22 + 23 + … + 2n + 2n+1, temos pela hipótese indutiva que:
P(n+1) = P(n) + 2n+1
Baseando-se na hipótese indutiva, temos P(n) = 20 + 21 + 22 + 23 + … + 2n = 2n+1 – 1
Assim:
P(n+1) = P(n) + 2n+1 = 2n+1 – 1 + 2n+1
Colocando-se em evidência:
2n+1 – 1 + 2n+1 = 2(2n+1) – 1 
= 2n+1+1 – 1
Portanto, 
P(n+1) = 2n+1+1 – 1
o que mostra P(n+1), c.q.d.
3
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
Exemplo 3
(Cavalcanti, UFPE)
Prove que P (n) :∑
i=0
n
x i=( x
n+1−1)
x−1
para todo o inteiro n ≥ 0 e para todo x real, sendo x ≠ 1.
Passo base:
Para P(0), tem-se ni = n0 = x0 = 1.
De fato, (x
0+1−1)
x −1
= ( x
1−1)
x −1
= 1 então a fórmula é verdadeira para n0.
Passo indutivo:
Temos que provar P (n+1) :∑
i=0
n+1
x i=( x
(n+1)+1−1)
x −1
Em outras palavras, se a fórmula é verdadeira para n = k, temos que provar para n = k+1, ou seja,
P(k) → P(k+1).
Hipótese indutiva:
Supondo que P (n) :∑
i=0
n
x i=( x
n+1−1)
x−1
é verdadeira, ou seja, P (k ):∑
i=0
k
x i=(x
k+1−1)
x −1
para k ≥ 0, 
deve-se mostrar que P (n) :∑
i=0
n+1
x i=( x
(n+1)+1−1)
x −1
=
(xn+2−1)
x −1
Podemos dizer que ∑
i=0
n+1
x i = ∑
i=0
n
xi+xn+1 (1)
ou fazendo a equivalência para n = k: ∑
i=0
k +1
x i = ∑
i=0
k
x i+xk +1
Pela hipótese indutiva podemos substituir ∑
i=0
n
x i por (x
n+1−1)
x −1 em (1) e assim:
 ∑
i=0
n+1
x i = ∑
i=0
n
xi+xn+1 = (x
n+1−1)
x −1
+x n+1
Fazendo o mínimo múltiplo comum para encontrarmos o mínimo denominador comum:
= (x
n+1−1)+(x −1) xn+1
x −1
= (x
n+1−1)+(x xn+1−xn+1)
x −1
= x
n+2−1
x −1
Portanto, P (n+1) :∑
i=0
n+1
x i=( x
(n+1)+1−1)
x −1
(c.q.d)
4
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
Exemplo 4
Prove por indução que: n! > 2 n-1, para n ≥ 3.
Passo base: 
Para n=3, temos:
3! > 2 3-1
6 > 2 2
6 > 4 
o que comprova a veracidade para o passo base.
Passo indutivo: temos que provar (n+1)! > 2n
Hipótese indutiva: Supondo n! > 2 n-1, para n ≥ 3 verdadeira, temos que provar (n+1)! > 2 (n+1)-1, 
para n ≥ 3
Sabe-se que: 
(n+1)! = (n+1).n! (1)
e 
2n = 21.2n-1 (2)
Multiplicando ambos lados da desigualdade n! > 2 n-1 por (n+1), temos:
(n+1).n! > (n+1).2n-1
Para n ≥ 3, (n+1) > 2 é verdadeira, então podemos considerar:
(n+1).n! > (n+1).2n-1 > 2.2n-1
Logo, (n+1).n! > 2.2n-1
Baseando-se em (2), temos:
(n+1).n! > 2n
Baseando-se em (1), temos:
(n+1)! > 2n
Portanto, (n+1)! > 2n é verdadeira (c.q.d.).
Exemplo 5
Prove que, para qualquer inteiro positivo n, 2n > n.
Passo base:
Para n=1, temos P(1) = 21> 1 é verdadeira.
5
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
Passo indutivo:
Temos que provar: P(n+1) = 2n+1> n+1
Hipótese indutiva: Considerando P(n) = 2n> n verdadeira, 
Reescrevendoo lado esquerdo da desigualdade, temos:
2n+1 = 21.2n
Multiplicando os dois lados da desigualdade 2n> n por 2, temos:
2n.2> n.2
Assim:
2n+1 = 2n.2> n.2
Sabendo que n.2 = n+n que por sua vez é maior ou igual a n+1, obtemos:
2n+1 = 2n.2 > 2.n = n + n ≥ n+1
2n+1 = 2n.2 > n+1
Logo, 2n+1 > n+1, c.q.d.
Exemplo 6
Prove por indução que n2 > 3n para n ≥ 4.
Passo base:
Para n=4, P(4) = 42 > 3.4 → 16 > 12 é verdadeira.
Passo indutivo: 
Temos que provar (n+1)2 > 3(n+1) para n ≥ 4.
Hipótese indutiva: Considerando n2 > 3n verdadeira para n ≥ 4, 
Reescrevendo o lado esquerdo da desigualdade, temos:
(n+1)2 = n2 + 2n + 1
Pela hipótese indutiva, n2 > 3n
Assim, somando-se 2n + 1 em ambos os lados da desigualdade, temos como verdadeira:
n2 + 2n + 1 > 3n + 2n + 1
Sendo n ≥ 4, temos que* 
n2 + 2n + 1 > 3n + 2n + 1
n2 + 2n + 1 ≥ 3n + 8 + 1 = 3n + 9
Sendo 3n + 9 > 3n + 3 = 3(n + 1)
Logo, (n + 1)2 > 3(n + 1), c.q.d.
6
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
* Note que não houve uma simples substituição de n por 4 na equação 3n + 2n + 1
Utilizou-se o princípio de que para qualquer n ≥ 4, 3n + 2n + 1 ≥ 3n + 8 + 1 = 3n + 9
Exemplo 7
(Marques, 2008)
Prove que (1+x)n ≥ 1 + x n, para x > 0, para todo n∈ℕ .
Passo base:
Para n = 1 temos:
(1 + x)1 ≥ 1 + x 1 
1 + x ≥ 1 + x
Logo a proposição é válida para o passo base.
Passo indutivo: Provar que (1 + x)n+1 ≥ 1 + x n+1 
Hipótese indutiva: Vamos considerar que (1+x)n ≥ 1 + x n, para x > 0, para todo n∈ℕ .
Temos então que:
(1 + x)n+1 ≥ 1 + x n+1 
(1 + x)n+1 = (1 + x)n (1 + x)1 
Pela hipótese da indução, temos: (1 + x)n (1 + x)1 ≥ (1 + x n) (1 + x) = 1 + x + x n + x n+1
Assim,
 (1 + x)n (1 + x)1 ≥ 1 + x + x n + x n+1 ≥ 1 + x n+1
(1 + x)n+1 ≥ 1 + x n+1
Logo, o resultado é válido para todo n∈ℕ .
Exemplo 8
Prove por indução que ∑
k=1
n 1
2k
< 1
Passo base:
Para n=1 temos:
∑
k=1
n 1
21
= 1
2
< 1 é verdadeira
Passo indutivo:
Deve-se demonstrar que ∑
k=1
n+1 1
2k
< 1
Hipótese indutiva: Considerando ∑
k=1
n 1
2k
< 1 verdadeira, aplicando-se o somatório até o termo 
n+1 temos:
7
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
∑
k=1
n+1 1
2k
= 1
21
+ 1
22
+ 1
23
+...+ 1
2(n+1)
< 1 colocando-se os termos em evidência a partir do segundo 
termo, temos:
∑
k=1
n+1 1
2k
= 1
2
+ 1
2( 121+ 122+...+ 12n) < 1 a expressão entre parênteses é o mesmo que ∑k=1
n 1
2k
, 
assim:
∑
k=1
n+1 1
2k
= 1
2
+ 1
2(∑k=1
n 1
2k ) < 1
Pela hipótese, temos que ∑
k=1
n 1
2k
< 1 é verdadeira, então, multiplicando-se ambos os lados por
1
2 tem-se: 
1
2∑k=1
n 1
2k
< 1
2
Dessa forma, ∑
k=1
n+1 1
2k
= 1
2
+ 1
2(∑k=1
n 1
2k ) < 1
Portanto, ∑
k=1
n+1 1
2k
< 1 é verdadeira (c.q.d.).
Exemplo 9
Seja f :ℕ⇒ℕ , tal que:
f (0) = 0
f (1) = 1
f (n) = f (n – 1) + f (n – 2), para n ≥ 2.
Prove por indução que f (n)≤(53)
n
Passo base:
Para n ≥ 2, temos:
f (2) = f (2 – 1) + f (2 – 2)
f (2) = f (1) + f (0)
f (2) = 1 + 0
Então f (2)=1≤(53)
2
, dado que 1≤(53)
2
=(259 )≈2,7
Portanto, a inequação é verdadeira para o caso base.
Passo indutivo:
Neste caso temos que fazer redução de T(β) para T(α) e em seguida provar que T(α) implica em
T(β).
8
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
Temos que provar f (k )≤( 53)
k
para k < n.
Hipótese indutiva: Considerando f (k )≤( 53)
k
verdadeira para k ≤ n, temos:
f (n) = f (n – 1) + f (n – 2) < (53)
n−1
+ (53)
n−2
(é válido pois (n – 1) < n e (n – 2) < n)
< (53)
n
.(53)
−1
+ (53)
n
.(53)
−2
Colocando em evidência:
< (53)
n
.((53)
−1
+ (53)
−2)
< (53)
n
.((35)+ ( 925))
< (53)
n
.(5.3+1.925 )
< (53)
n
.(2425)
Logo, f (n)< 24
25(53)
n
< (53)
n
é verdadeira, dado que (2425)=0,96
Portanto, f (n)≤(53)
n
, c.q.d.
Exemplo 10
Prove por indução que 3 é divisor de P(n): n3 – n.
Passo base:
Para n = 1, P(1) = 13 – 1 = 0 → 0/3 = 0 é verdadeira.
Passo indutivo:
Temos que provar que 3 é divisor de (n+1)3 – (n+1).
Hipótese indutiva: Suponha que 3 é divisor de n3 – n seja verdadeira.
Desenvolvendo (n+1)3 – (n+1):
(n+1)3 – (n+1) = n3 + 3n2 + 3n +1 – (n + 1) 
 = n3 + 3n2 + 3n +1 – n – 1
 = n3 – n + 3n2 + 3n
 
Pela hipótese indutiva, 3 é divisor de n3 – n. Como 3 também é divisor de 3n2 + 3n, então 3 é divisor
de n3 – n + 3n2 + 3n = (n+1)3 – (n+1), c.q.d.
9
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
Exemplo 11
(Cavalcanti, UFPE)
Prove por indução que P(n):22n – 1 é divisível por 3, para n ≥ 1.
Passo base:
P(1) = 22.1 – 1 = 4 – 1 = 3, em que 3 é divisível por 3.
Passo indutivo:
Temos que provar que 22(n+1) – 1 é divisível por 3.
Hipótese indutiva: Considerando que 22n – 1 divisível por 3 seja verdadeira. Ser divisível por 3
significa 22n – 1 = 3m, para algum inteiro m, ou seja, 22n = 3m + 1.
22(n+1) – 1 = 22n+2 – 1 
= 22.22n – 1 → pela hipótese indutiva, temos:
= 22.(3m + 1) – 1 
= 4.(3m + 1) – 1 
= 12m + 4 – 1 
= 12m + 3
= 3(4m+1) 
Sendo 4m+1 um número inteiro, portanto, 22(n+1) – 1 é divisível por 3, c.q.d.
Exemplo 12
Prove que P(n): 23n – 1 é divisível por 7 para todo inteiro positivo.
Passo base:
Para n=1, P(1) = 23.1 – 1 = 8 – 1 = 7. 
7 é divisível por 7, portanto, P(1) é verdadeira.
Passo indutivo: 
Temos que provar que 23(n+1) – 1 é divisível por 7 para todo inteiro positivo.
Hipótese indutiva: Suponha que 23n – 1 é divisível por 7 seja verdadeira. Ser divisível por 7
significa que 23n – 1 = 7m, para algum inteiro m, ou seja, 23n = 7m + 1. 
 23(n + 1) – 1 = 23n + 3 – 1
= 23 23n – 1 ← pela hipótese indutiva, temos:
= 23 (7m + 1) – 1 ← distribuindo:
= 23 .7m + 8 – 1
= 23 .7m + 7 ← colocando em evidência:
= 7(23 m +1)
Sendo 23 m +1 um número inteiro, portanto, 23(n + 1) – 1 é divisível por 7, c.q.d.
10
Prof.ª Juliana Keiko Yamaguchi (DIN/UEM)
Exercícios
1) Use indução matemática para provar que a proposição a seguir é verdadeira para todo inteiro
positivo n.
2 + 4 + 6 + … + 2n = n(n+1)
2) Prove que n2 ≥ 2n + 3 para n ≥ 3.
3) Prove que 32n + 7 é divisível por 8.
Referências
CAVALCANTI, George Darmiton da Cunha. Indução Matemática. Centro de Informática – UFPE.
HEFEZ, Abramo. Indução Matemática. Departamento de Matemática Aplicada, Universidade
Federal Fluminense, 2007
MARQUES, Mauro S. de F., Fundamentos de Matemática – Indução Matemática. 2008. 
REAL, Eduardo Machado. O Importante Papel da Indução Matemática e suas Estratégias no Projeto
de Algoritmos Recursivos. Universidade Estadual De Mato Grosso Do Sul – V Seminário de
Educação Matemática de Nova Andradina, 2013.
11
	Fundamentos matemáticos: Indução Matemática
	Exemplo 1
	Exemplo 2
	Exemplo 3
	Exemplo 4
	Exemplo 5
	Exemplo 6
	Exemplo 7
	Exemplo 8
	Exemplo 9
	Exemplo 10
	Exemplo 11
	Exemplo 12
	Referências