Lista 1

Prévia do material em texto

1
Matema´tica Discreta I
Lista 01: Recorreˆncias e Induc¸a˜o
• Princ´ıpio da Induc¸a˜o Finita
Seja a um inteiro e P (n) uma proposic¸a˜o sobre n para cada n ≥ a. Enta˜o se
(i) P (a) e´ verdadeira (Base de induc¸a˜o), e
(ii) para todo inteiro k ≥ a, P (k) =⇒ P (k + 1) (Passo indutivo),
enta˜o P (n) e´ verdadeira para todo inteiro n ≥ a.
• Induc¸a˜o Completa
Se
(i) P (a) e´ verdadeira (Base de induc¸a˜o), e
(ii) para todo inteiro, (P (a) e P (a+ 1) e . . . e P (k)) =⇒ P (k + 1) (Passo indutivo),
enta˜o P (n) e´ verdadeira para todo inteiro n ≥ a.
• Coeficientes Binomiais
Relembrando: (
n
k
)
def
= nu´mero de subconjuntos S ⊂ {1, 2, . . . , n} com k elementos
=
k fatores︷ ︸︸ ︷
n · (n− 1) · (n− 2) · · · (n− k + 1)
k!
=
n!
k!(n− k)! (para n inteiro na˜o negativo)
O s´ımbolo
(
n
k
)
leˆ-se n escolhe k (n choose k in English) porque ele conta o nu´mero de maneiras de se
escolher um subconjunto de k elementos de um conjunto com n elementos.
01. Ler o cap´ıtulo 5 (Induc¸a˜o e Fermat), sec¸o˜es 1 e 2, e a introduc¸a˜o do livro “Nu´meros Inteiros e
Criptografia RSA”. Fac¸a os exerc´ıcios de 1 a 5 da pa´gina 100.
02. No problema das Torres de Hano´i, determine (com prova!) o nu´mero mı´nimo de movimentos Rn se
movimentos “diretos” A⇒ C na˜o sa˜o permitidos (i.e., todo movimento utiliza o pino B).
03. No problema das Torres de Hano´i, encontre uma recursa˜o para o nu´mero mı´nimo de movimentos Qn
se os discos so´ podem ser movidos “em sentido hora´rio” A⇒ B ⇒ C ⇒ A, ou seja, do pino A para o B,
do B para o C, do C para o A.
Observac¸a˜o: Neste problema, basta encontrar a recursa˜o, vamos aprender a resolveˆ-la mais tarde.
04. Qual o nu´mero ma´ximo de regio˜es determinadas por n retas em um plano?
05. Qual e´ o nu´mero ma´ximo de regio˜es do espac¸o determinadas por n planos?
06. Prove que, para todos os inteiros n, k ≥ 0,(
n
k − 1
)
+
(
n
k
)
=
(
n+ 1
k
)
Voceˆ pode dar uma prova alge´brica ou combinato´ria para esta identidade (deˆ as duas de prefereˆncia).
07. Seja n um nu´mero natural. Demonstre as seguintes identidades utilizando o PIF:
(a) 12 + 22 + 32 + · · ·+ n2 = n·(n+ 12 )·(n+1)3 (b) 13 + 23 + 33 + · · ·+ n3 = (1 + 2 + 3 + · · ·+ n)2
(c) n3 − n e´ um mu´ltiplo de 6 (d) n(n2 − 1)(3n+ 2) e´ um mu´ltiplo de 24
(e) 25n − 1 e´ um mu´ltiplo de 12 (f) 2n + 1 e´ um mu´ltiplo de 3 se n e´ ı´mpar
(g) 12n − 1 e´ um mu´ltiplo de 11 (h) 2n + n e´ um mu´ltiplo de 3 se n esta´ na PA 1, 7, 13, . . .
(i) 2n < n! para n ≥ 4 (j) 2n3 > 3n2 + 3n+ 1 para n ≥ 4
2
(k)
(
n
0
)
+
(
n
1
)
+ · · ·+ (nn) = 2n (l) (nn)+ (n+1n )+ (n+2n )+ · · ·+ (n+kn ) = (n+k+1n+1 )
(m) (fo´rmula de Moivre) (cosx+ i senx)n = cosnx+ i sennx para todo x ∈ R
(n) senx+ sen 2x+ · · ·+ sennx = sen((n+ 1)x/2) · sen(nx/2)
sen(x/2)
para todo x ∈ R
Deˆ uma interpretac¸a˜o combinato´ria para (i).
08. Um plano e´ dividido em regio˜es por n retas em posic¸a˜o geral (isto e´, na˜o ha´ 3 retas concorrentes em
um mesmo ponto). Mostre que estas regio˜es podem ser coloridas com duas cores de modo que regio˜es
vizinhas (isto e´, regio˜es que fazem fronteira em um segmento de reta) tenham cores diferentes.
09. Utilize o PIF e prove o binoˆmio de Newton: para quaisquer a, b reais e n natural
(a+ b)n =
(
n
0
)
a0bn +
(
n
1
)
a1bn−1 +
(
n
2
)
a2bn−2 + · · ·+
(
n
n
)
anb0
10. A sequ¨eˆncia de Fibonacci Fn e´ definida por
Fn =
{ 0 se n = 0
1 se n = 1
Fn−2 + Fn−1 se n > 1
Os primeiros termos desta sequ¨eˆncia sa˜o portanto 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .. Mostre que, para
todo n natural,
(a)
F1 + F2 + · · ·+ Fn = Fn+2 − 1
(b) (
n
0
)
+
(
n− 1
1
)
+
(
n− 2
2
)
+
(
n− 3
3
)
+ · · · = Fn+1
(c)
Fn =
αn − βn
α− β
onde α = 1+
√
5
2 e β =
1−√5
2 sa˜o as ra´ızes de x
2 = x+ 1.
11. Considere a matriz
A =
(
1 1
1 0
)
Determine, com prova, uma fo´rmula expl´ıcita para An.
12. (Pequeno Teorema de Fermat) Seja p um nu´mero primo e n um inteiro qualquer. Prove que
np − n e´ um mu´ltiplo de p.
Dica: Utilize o binoˆmio de Newton e mostre que se 0 < k < p enta˜o
(
p
k
)
e´ divis´ıvel por p.
13. Considere a recorreˆncia (Nu´meros de Knuth)
K0 = 1; Kn+1 = 1 + min(2Kbn2 c, 3Kbn3 c), n ≥ 0.
Prove que Kn ≥ n. Aqui bxc denota a parte inteira de x, i.e., o maior inteiro que e´ menor ou igual a
x.
14. Prove que, para todo inteiro n > 1,
(a)
√
n <
1√
1
+
1√
2
+ · · ·+ 1√
n
< 2
√
n, n > 1.
(b)
1 +
1
22
+
1
32
+ · · ·+ 1
n2
>
3n
2n+ 1
.
3
15. A seguinte prova por induc¸a˜o parece correta, mas por alguma raza˜o temos que, para n = 6,
1
2
+
1
6
+
1
12
+
1
20
+
1
30
=
5
6
,
e
3
2
− 1
6
=
4
3
.
Onde esta´ o erro?
“Teorema:
1
1× 2 +
1
2× 3 + · · ·+
1
(n− 1)× n =
3
2
− 1
n
.
Demonstrac¸a˜o: No´s faremos uma induc¸a˜o sobre n. Para n = 1, 32 − 1n = 11×2 ; e assumindo que o
teorema e´ va´lido para n,
1
1× 2 + · · ·+
1
(n− 1)× n +
1
n× (n+ 1)
=
3
2
− 1
n
+
1
n(n+ 1)
=
3
2
− 1
n
+
(
1
n
− 1
n+ 1
)
=
3
2
− 1
n+ 1
.”
16. Ha´ algo errado com a seguinte demonstrac¸a˜o, o que e´?
“Teorema: Seja a um nu´mero positivo. Para todo inteiro positivo n no´s temos an−1 = 1.
Demonstrac¸a˜o: Se n = 1, an−1 = a1−1 = a0 = 1. E por induc¸a˜o, assumindo que o teorema e´
verdadeiro para 1, 2, . . . , n, no´s temos
a(n+1)−1 = an =
an−1 · an−1
an−2
=
1× 1
1
= 1;
donde o teorema e´ verdadeiro para n+ 1 tambe´m.”
17. Aqui esta´ uma prova por induc¸a˜o que se x, y ∈ N, enta˜o x = y.
O que esta´ errado?
Demonstrac¸a˜o: Nossa induc¸a˜o sera´ sobre max(x, y). Para max(x, y) = 0, o resultado e´ claramente
verdadeiro. Assuma o resultado para max(x, y) = k, e seja max(x, y) = k+1. Sejam x1 = x−1, y1 = y−1.
Enta˜o max(x1, y1) = k. Pela hipo´tese de induc¸a˜o, x1 = y1 e, portanto, x = x1 + 1 = y1 + 1 = y. CQD