inducao matematica

Prévia do material em texto

Sumário
Revisão:	Indução	Matemá4ca	
Método	da	subs4tuição	para	resolver	
recorrências
1
Como saber se todas 
as pedras caíram? 
2
Se o 1º. cair, o segundo tem que cair também
3
Se o 2º. cair, o terceiro tem que cair também
4
Se o k-ésimo dominó cair, 
o (k+1)-ésimo deve cair também
5
Se o k-ésimo dominó cair, 
o (k+1)-ésimo deve cair também
Para afirmar que todos os dominós cairão, 
temos que garantir duas coisas
O 1º. Dominó deve cair
6
Somatório dos 
primeiros n inteiros
1																											=		1	
1	+	2																					=	3																
1	+	2	+	3														=	6
1	+	2	+	3	+	4							=	10
1	+	2	+	3	+	4	+	5	=	15
7
1																											=		1															=	1	x 2	/	2
1	+	2																					=	3																=	2	x 3	/	2
1	+	2	+	3														=	6																=	3	x 4	/	2
1	+	2	+	3	+	4							=	10															=	4	x 5	/	2
1	+	2	+	3	+	4	+	5	=	15															=	5	x 6	/	2
1	+	2	+	3	+	4	+	...	+	n =	n (	n+1)	 /	2
8
n=1
1	=	
1x2/2
1	+	2	+	3	+	4	+	...	+	n =	n (	n+1)	 /	2
n=2 n=3											n=4										n=5								
...
1	+	2	=	
2x3/2
1+2+3	=	
3x4/2
1+2+3+4	=	
4x5/2
1+2+3+4+5	=	
5x6/2
9
n=1
1	=	
1x2/2
1	+	2	+	3	+	4	+	...	+	n =	n (	n+1)	 /	2
n=2 n=3											n=4										n=5								
...
1	+	2	=	
2x3/2
1+2+3	=	
3x4/2
1+2+3+4	=	
4x5/2
1+2+3+4+5	=	
5x6/2
Isso	deve	ser	verdade
10
n=k
1+2+3+...+k =	
k(k+1)/n
n=k+1
1+2+3+...+k+1=	
(k+1)(k+2)/2
1	+	2	+	3	+	4	+	...	+	n =	n (	n+1)	 /	2
11
2
1+2+3+...+n =	n(n+1)/2 Para	n =	1,	2,	3,	...
Afirmação	que	queremos	provar!
1
n =	1
Lado	direito:	1	
Lado	esquerdo:	1(1x2)/2	=	1
2
Se					1+2+3+...+k =	k(k+1)/2
Então	
1+2+3+...+k+(k+1)	=	(k+1)(k+2)/2
Hipótese	indutiva
= k(k+1)/2	+	(k+1)
= (k+1)(k+2)/2
= (k(k+1)	+	2(k+1))/2
12
n = 1
1 = 1*(1 + 1)/2 
= 2/2 = 1
1 + 2 +3 +…+k = k(k+1)/2
1 + 2 + 3 +..+ k + k+1 = (k+1)(k+2)/2 
k(k+1)/2 + k+ 1 = (k+1)(k+2)/2 
(k(k+1) + 2k + 2)/2 = (k^2 + 2k + k + 2)/2 
(k^2 + k + 2k + 2)/2 = (k^2 + 2k + k + 2)/2 
1+2+3+...+n =	n(n+1)/2 Para	n =	1,	2,	3,	...
Afirmação	que	queremos	provar!
1
n =	1
Lado	direito:	1	
Lado	esquerdo:	1(1x2)/2	=	1
2
Se					1+2+3+...+k =	k(k+1)/2
Então	
1+2+3+...+k+(k+1)	=	(k+1)(k+2)/2
Hipótese	de	indução
= k(k+1)/2	+	(k+1)
= (k+1)(k+2)/2Portanto, pelo princípio da matemática indutiva,
1+2+3+...+n = n(n+1)/2 para n = 1,2,3,...
13