Lista 4 - Matemática Discreta 2021-2

UFLA – ICET Departamento de Matem´atica e Matem´atica Aplicada Prof. Jamil Abreu UFLA/ICET/DMM Sala 10 Telefone: +55-35-3821-1643 E-mail: jamil.abreu@ufla.br Matem´atica Discreta (2021/2) – Lista n◦04 – Ex. 1. Demonstre as seguintes identidades por indu¸c˜ao. (a) 1 + 3 + · · · + (2n − 1) = n2; (b) 12 + 22 + · · · + n2 = n(n + 1)(2n + 1) 6 ; (c) 13 + 23 + · · · + n3 = (1 + 2 + · · · + n)2; (d) 12 + 42 + 72 + · · · + (3n − 2)2 = n(6n2 − 3n − 1) 2 ; (e) 1 · 2 + 2 · 3 + · · · + n(n + 1) = n(n + 1)(n + 2) 3 ; (f) 1 1 · 2 + 1 2 · 3 + · · · + 1 n(n + 1) = 1 − 1 n + 1. ▲ Ex. 2. Note o seguinte: 1 = 1, 1 − 4 = −(1 + 2), 1 − 4 + 9 = 1 + 2 + 3, 1 − 4 + 9 − 16 = −(1 + 2 + 3 + 4). Imagine a lei geral sugerida pelas identidades acima e demonstre-a por indu¸c˜ao. ▲ Ex. 3. Note que 1 + 1 2 = 2 − 1 2, 1 + 1 2 + 1 4 = 2 − 1 4, 1 + 1 2 + 1 4 + 1 8 = 2 − 1 8. Imagine a regra geral e prove por indu¸c˜ao. ▲ 1 Ex. 4. Mostre por indu¸c˜ao matem´atica o teorema de geometria plana segundo o qual a soma dos ˆangulos internos de um pol´ıgono convexo de n lados ´e igual a (n − 2) · 180◦. ▲ Ex. 5. Mostre por indu¸c˜ao matem´atica que an − bn ´e sempre divis´ıvel por a − b, para todo natural n. ▲ Ex. 6. Considere a sequˆencia de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, . . . em que todo elemento depois do segundo ´e a soma dos dois anteriores que o precedem. Assim, se o n-´esimo termo ´e fn, a sequˆencia de Fibonacci ´e definida pelas condi¸c˜oes: f1 = 1, f2 = 1, fn = fn−1 + fn−2 (n = 3, 4, . . . ). (Isto ´e um exemplo de defini¸c˜ao recursiva, sobre a qual falaremos mais adiante.) Mostre que quaisquer dois termos sucessivos nunca possuem um fator comum maior do que 1. (Ou seja, mostre por indu¸c˜ao: para todo n, fn e fn+1 n˜ao possuem fator comum maior do que 1.) ▲ Ex. 7. Sejam a1, a2, . . . n´umeros reais positivos tais que, para alguma constante c > 0, an ⩽ can−1 para todo n > 1. Mostre por indu¸c˜ao que an ⩽ a1cn−1 para todo n ⩾ 1. ▲ Ex. 8 (Algoritmo da divis˜ao). Seja b um n´umero natural. Mostre por indu¸c˜ao que para todo n ∈ N existem naturais q e r tais que n = qb + r e 0 ⩽ r < b. ▲ Ex. 9. Mostre, por indu¸c˜ao, que 12 + 22 + · · · + (n − 1)2 < n3 3 para todo n natural. ▲ Ex. 10. Mostre por indu¸c˜ao: se a1, a2 . . . , an s˜ao quaisquer n n´umeros reais positivos, todos com mesmo sinal e maiores do que −1 ent˜ao (1 + a1)(1 + a2) · · · (1 + an) ⩾ 1 + a1 + a2 · · · + an. Deduza a desigualdade de Bernoulli: se x > −1 e n ∈ N ent˜ao (1 + x)n ⩾ 1 + nx e, para n > 1, ocorre igualdade se e somente se x = 0. ▲ Ex. 11. A desigualdade da m´edia ´e a afirma¸c˜ao de que, para quaisquer n´umeros positivos x1, . . . , xn, vale a estimativa (x1 · · · xn)1/n ⩽ x1 + · · · + xn n . A express˜ao `a esquerda ´e a m´edia geom´etrica dos xi’s e a express˜ao `a direita ´e a m´edia aritm´etica. Neste exerc´ıcio, demonstramos a desigualdade da m´edia a partir da desigualdade de Bernoulli (exerc´ıcio anterior).(1) 1Este exerc´ıcio foi adaptado dos artigos “M. D. Hirschhorn, The AM-GM Inequality, Math. Intelligencer 29, 7 (2007)” e “L. Maligranda, The AM-GM Inequality is Equivalent to the Bernoulli Inequality, Math. Intelligencer 34, 1 (2012)”. 2 (a) Deduza de desigualdade de Bernoulli que wt! > (n+l1jyr—n (n€N, x>0). (b) Sejam 21,...,2%p41 > 0. Escreva Lyre + ILn41 Ly r++ @n a = ———————_ e 9 = ————__.. n+1 n Pondo « = a/b na desigualdade em (a), deduza que (Hy Se (Hate) n+ 1 Zz 4n+1 n . (c) Demonstre a desigualdade da média por inducgao matematica, usando (b) para o passo indutivo. A Ex. 12. Ache a falacia na “demonstracao” por inducao da seguinte afirmacao: “Todos os numeros num conjunto de n elementos sao iguais uns aos outros.” Denote a proposigaéo acima por P(n). Obviamente, P(1) é verdadeira. Suponha P(k) valida para algum k. Considere um conjunto de k + 1 elementos, digamos {a1,d2,...,@z41}. O conjunto {a1,d2,...,a,} tem k elementos, logo a; = ag = -:: = dy pela hipdtese indutiva; da mesma forma, {d2,a@3,...,@%41} tem k elementos, logo ag = a3 = ++: = ag41 também pela hipotese indutiva. Segue que aj = a3 = --- = dg41, portanto P(k + 1) é verdadeira. Por inducgao, P(n) é verdadeira para todo n. A 3