Princípio da indução matemática

Prévia do material em texto

Princ´ıpio da induc¸a˜o matema´tica
Thadeu Ribeiro Benicio Milfont
Semestre 2016-2
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
1 Suma´rio
2 Princ´ıpio de induc¸a˜o matema´tica
Teorema de Induc¸a˜o (Primeira Forma)
Exemplos de Induc¸a˜o (Primeira Forma)
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Teorema de Induc¸a˜o (1a Forma)
Considere a seguinte afirmac¸a˜o: Para todo n ∈ N, vale que
Sn = 1 + 2 + ... + n = n(n+1)2 . Como provar que essa afirmac¸a˜o e´
verdadeira?
Teorema de Induc¸a˜o (1a Forma): Suponha que seja dada
uma afirmac¸a˜o a(n) para todo n ≥ m, que depende de n ∈ N,
tal que:
(i) a(m) e´ verdade.
(ii) Para k ∈ N, a(k + 1) e´ verdade sempre que a(k)
for verdadeira. Enta˜o, a(n) e´ verdadeira para
todo n ≥ m natural.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Teorema de Induc¸a˜o (1a Forma)
Considere a seguinte afirmac¸a˜o: Para todo n ∈ N, vale que
Sn = 1 + 2 + ... + n = n(n+1)2 . Como provar que essa afirmac¸a˜o e´
verdadeira?
Teorema de Induc¸a˜o (1a Forma): Suponha que seja dada
uma afirmac¸a˜o a(n) para todo n ≥ m, que depende de n ∈ N,
tal que:
(i) a(m) e´ verdade.
(ii) Para k ∈ N, a(k + 1) e´ verdade sempre que a(k)
for verdadeira. Enta˜o, a(n) e´ verdadeira para
todo n ≥ m natural.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos de Induc¸a˜o (Primeira Forma)
Passos da prova:
1-Mostrar que P(m) e´ verdade;
2-Escrever P(k) hipo´tese de induc¸a˜o;
3-Mostrar que P(k + 1) e´ verdade.
Problema(1):Prove por induc¸a˜o que para todo n ∈ N;
Sn = 1 + 2 + ... + n = n(n+1)2 ;
Problema(2):Prove por induc¸a˜o que para todo n ∈ N;
Sn = 2 + 4 + 6 + ... + 2n = n(n + 1);
Problema (3):Prove por induc¸a˜o que se n ∈ N; enta˜o n3 − n e´
multiplo de 3;
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos de Induc¸a˜o (Primeira Forma)
Passos da prova:
1-Mostrar que P(m) e´ verdade;
2-Escrever P(k) hipo´tese de induc¸a˜o;
3-Mostrar que P(k + 1) e´ verdade.
Problema(1):Prove por induc¸a˜o que para todo n ∈ N;
Sn = 1 + 2 + ... + n = n(n+1)2 ;
Problema(2):Prove por induc¸a˜o que para todo n ∈ N;
Sn = 2 + 4 + 6 + ... + 2n = n(n + 1);
Problema (3):Prove por induc¸a˜o que se n ∈ N; enta˜o n3 − n e´
multiplo de 3;
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos de Induc¸a˜o (Primeira Forma)
Passos da prova:
1-Mostrar que P(m) e´ verdade;
2-Escrever P(k) hipo´tese de induc¸a˜o;
3-Mostrar que P(k + 1) e´ verdade.
Problema(1):Prove por induc¸a˜o que para todo n ∈ N;
Sn = 1 + 2 + ... + n = n(n+1)2 ;
Problema(2):Prove por induc¸a˜o que para todo n ∈ N;
Sn = 2 + 4 + 6 + ... + 2n = n(n + 1);
Problema (3):Prove por induc¸a˜o que se n ∈ N; enta˜o n3 − n e´
multiplo de 3;
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos de Induc¸a˜o (Primeira Forma)
Passos da prova:
1-Mostrar que P(m) e´ verdade;
2-Escrever P(k) hipo´tese de induc¸a˜o;
3-Mostrar que P(k + 1) e´ verdade.
Problema(1):Prove por induc¸a˜o que para todo n ∈ N;
Sn = 1 + 2 + ... + n = n(n+1)2 ;
Problema(2):Prove por induc¸a˜o que para todo n ∈ N;
Sn = 2 + 4 + 6 + ... + 2n = n(n + 1);
Problema (3):Prove por induc¸a˜o que se n ∈ N; enta˜o n3 − n e´
multiplo de 3;
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 1: Queremos mostrar que
Sn = 1 + 2 + 3 +⋯+ n = n(n + 1)
2
para todo n ∈ N. Seguindo os
passos do teorema temos que:
Para n = 1, temos S1 = 1(1 + 1)
2
= 1, a fo´rmula e´ verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
Sk = k(k + 1)
2
, devemos mostrar que a fo´rmula e´ verdadeira
para n = k + 1 ou seja, Sk+1 = (k + 1)[(k + 1) + 1]
2
;
Da´ı, Sk+1 = 1 + 2 + 3 +⋯ + k + (k + 1) = k(k + 1)
2
+ (k + 1) =(k + 1)[(k + 1) + 1]
2
, como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 1: Queremos mostrar que
Sn = 1 + 2 + 3 +⋯+ n = n(n + 1)
2
para todo n ∈ N. Seguindo os
passos do teorema temos que:
Para n = 1, temos S1 = 1(1 + 1)
2
= 1, a fo´rmula e´ verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
Sk = k(k + 1)
2
, devemos mostrar que a fo´rmula e´ verdadeira
para n = k + 1 ou seja, Sk+1 = (k + 1)[(k + 1) + 1]
2
;
Da´ı, Sk+1 = 1 + 2 + 3 +⋯ + k + (k + 1) = k(k + 1)
2
+ (k + 1) =(k + 1)[(k + 1) + 1]
2
, como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 1: Queremos mostrar que
Sn = 1 + 2 + 3 +⋯+ n = n(n + 1)
2
para todo n ∈ N. Seguindo os
passos do teorema temos que:
Para n = 1, temos S1 = 1(1 + 1)
2
= 1, a fo´rmula e´ verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
Sk = k(k + 1)
2
, devemos mostrar que a fo´rmula e´ verdadeira
para n = k + 1 ou seja, Sk+1 = (k + 1)[(k + 1) + 1]
2
;
Da´ı, Sk+1 = 1 + 2 + 3 +⋯ + k + (k + 1) = k(k + 1)
2
+ (k + 1) =(k + 1)[(k + 1) + 1]
2
, como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 1: Queremos mostrar que
Sn = 1 + 2 + 3 +⋯+ n = n(n + 1)
2
para todo n ∈ N. Seguindo os
passos do teorema temos que:
Para n = 1, temos S1 = 1(1 + 1)
2
= 1, a fo´rmula e´ verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
Sk = k(k + 1)
2
, devemos mostrar que a fo´rmula e´ verdadeira
para n = k + 1 ou seja, Sk+1 = (k + 1)[(k + 1) + 1]
2
;
Da´ı, Sk+1 = 1 + 2 + 3 +⋯ + k + (k + 1) = k(k + 1)
2
+ (k + 1) =(k + 1)[(k + 1) + 1]
2
, como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 2: Queremos mostrar que
Sn = 2+ 4+ 6+⋯+ 2n = n(n + 1) para todo n ∈ N. Seguindo os
passos do teorema temos que:
Para n = 1, temos S1 = 1(1 + 1) = 2, a fo´rmula e´ verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
Sk = k(k + 1), devemos mostrar que a fo´rmula e´ verdadeira
para n = k + 1 ou seja, Sk+1 = (k + 1)[(k + 1) + 1];
Da´ı, Sk+1 = 2 + 4 + 6 +⋯ + 2k + 2(k + 1) =
k(k + 1) + 2(k + 1) = (k + 1)[(k + 1) + 1], como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 2: Queremos mostrar que
Sn = 2+ 4+ 6+⋯+ 2n = n(n + 1) para todo n ∈ N. Seguindo os
passos do teorema temos que:
Para n = 1, temos S1 = 1(1 + 1) = 2, a fo´rmula e´ verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
Sk = k(k + 1), devemos mostrar que a fo´rmula e´ verdadeira
para n = k + 1 ou seja, Sk+1 = (k + 1)[(k + 1) + 1];
Da´ı, Sk+1 = 2 + 4 + 6 +⋯ + 2k + 2(k + 1) =
k(k + 1) + 2(k + 1) = (k + 1)[(k + 1) + 1], como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 2: Queremos mostrar que
Sn = 2+ 4+ 6+⋯+ 2n = n(n + 1) para todo n ∈ N. Seguindo os
passos do teorema temos que:
Para n = 1, temos S1 = 1(1 + 1) = 2, a fo´rmula e´ verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
Sk = k(k + 1), devemos mostrar que a fo´rmula e´ verdadeira
para n = k + 1 ou seja, Sk+1 = (k + 1)[(k + 1) + 1];
Da´ı, Sk+1 = 2 + 4 + 6 +⋯ + 2k + 2(k + 1) =
k(k + 1) + 2(k + 1) = (k + 1)[(k + 1) + 1], como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 2: Queremos mostrar que
Sn = 2+ 4+ 6+⋯+ 2n = n(n + 1) para todo n ∈ N. Seguindo os
passos do teorema temos que:
Para n = 1, temos S1 = 1(1 + 1) = 2, a fo´rmula e´ verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
Sk = k(k + 1), devemos mostrar que a fo´rmula e´ verdadeira
para n = k + 1 ou seja, Sk+1 = (k + 1)[(k + 1) + 1];
Da´ı, Sk+1 = 2 + 4+ 6 +⋯ + 2k + 2(k + 1) =
k(k + 1) + 2(k + 1) = (k + 1)[(k + 1) + 1], como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 3: Se n e´ natural, enta˜o n3 − n e´
multiplo de 3.
Para n = 1, temos 13 − 1 e´ multiplo de 3, a afirmac¸a˜o e´
verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
k3 − k e´ multiplo de 3, devemos mostrar que a fo´rmula e´
verdadeira para n = k + 1 ou seja, que (k + 1)3 − (k + 1) e´
multiplo de 3.
Mas como(k +1)3−(k +1) = k3+3k2+3k +1−k −1 = (k3−K)+3(k2+k)
que e´ multiplo de 3, pois por hipo´tese k3 − k e´ multiplo de 3 e
3(k2 + k) tambe´m e´ multiplo de 3, como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 3: Se n e´ natural, enta˜o n3 − n e´
multiplo de 3.
Para n = 1, temos 13 − 1 e´ multiplo de 3, a afirmac¸a˜o e´
verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
k3 − k e´ multiplo de 3, devemos mostrar que a fo´rmula e´
verdadeira para n = k + 1 ou seja, que (k + 1)3 − (k + 1) e´
multiplo de 3.
Mas como(k +1)3−(k +1) = k3+3k2+3k +1−k −1 = (k3−K)+3(k2+k)
que e´ multiplo de 3, pois por hipo´tese k3 − k e´ multiplo de 3 e
3(k2 + k) tambe´m e´ multiplo de 3, como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 3: Se n e´ natural, enta˜o n3 − n e´
multiplo de 3.
Para n = 1, temos 13 − 1 e´ multiplo de 3, a afirmac¸a˜o e´
verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
k3 − k e´ multiplo de 3, devemos mostrar que a fo´rmula e´
verdadeira para n = k + 1 ou seja, que (k + 1)3 − (k + 1) e´
multiplo de 3.
Mas como(k +1)3−(k +1) = k3+3k2+3k +1−k −1 = (k3−K)+3(k2+k)
que e´ multiplo de 3, pois por hipo´tese k3 − k e´ multiplo de 3 e
3(k2 + k) tambe´m e´ multiplo de 3, como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
Exemplos
Soluc¸a˜o do Problema 3: Se n e´ natural, enta˜o n3 − n e´
multiplo de 3.
Para n = 1, temos 13 − 1 e´ multiplo de 3, a afirmac¸a˜o e´
verdadeira;
Suponha que a fo´rmula seja verdadeira para n = k ou seja,
k3 − k e´ multiplo de 3, devemos mostrar que a fo´rmula e´
verdadeira para n = k + 1 ou seja, que (k + 1)3 − (k + 1) e´
multiplo de 3.
Mas como(k +1)3−(k +1) = k3+3k2+3k +1−k −1 = (k3−K)+3(k2+k)
que e´ multiplo de 3, pois por hipo´tese k3 − k e´ multiplo de 3 e
3(k2 + k) tambe´m e´ multiplo de 3, como queriamos.
Thadeu Ribeiro Benicio Milfont Princ´ıpio da induc¸a˜o matema´tica
	Sumário
	Princípio de indução matemática
	Teorema de Indução (Primeira Forma) 
	Exemplos de Indução (Primeira Forma)