induçao

64

Demonstrações, Recursão e Análise de Algoritmo

Exercícios 2.2
Nos Exercícios 1 a 16, use a indução matemática para demonstrar que os resultados são válidos para qualquer inteiro positivo n.

onde n ! é o produto dos n inteiros positivos de 1 até n.
17. Uma progressão geométrica (seqüência geométrica) é uma seqüência de termos onde existe um termo inicial a, e cada termo subseqüente é obtido pelo produto do anterior por um valor constante r. Prove que a fórmula para a soma dos n primeiros termos de uma seqüência geométrica é: Seção 2.2 Indução

65

18. Uma progressão aritmética (seqüência aritmética) é uma seqüência de termos onde existe um termo inicial a e cada termo subseqüente é obtido pela soma de um valor constante d ao termo anterior. Prove que a fórmula da soma dos n primeiros termos de uma seqüência aritmética é: 19. Prove que n2 > n + 1 para n

2.

20. Prove que n2 > 5n + 10 para n > 6.
21. Prove que 2n > n2 para n

5.

22. Prove que n! > n2 para n

4, onde n! é o produto dos inteiros positivos de 1 a n.

23. Prove que 2n < n! para n

4.

24. Prove que n! < nn para n

2.

25. Prove que (1 +x)n > 1 + xn para n > 1, x > 0.
26. Prove que

para n

1 e 0 < a < b.

27. Prove que 1 + 2 + .... + n < n2 para n > 1.
28. a. Tente usar a indução para provar que

O que deu errado?
b. Prove que

mostrando assim que

Para os Exercícios 29 a 40, prove que as sentenças são verdadeiras para todo inteiro positivo.
29. 23" — 1 é divisível por 7.
30. 32" + 7 é divisível por 8.
31. 7n — 2né divisível por 5.
32. 13n — 6n é divisível por 7.
33. 2n + (-1) n+1 é divisível por 3.
34. 25n+l + 5n+2 é divisível por 27.
35. 3 4n+2 + 52"+l é divisível por 14.
36. 72n + 16n - 1 é divisível por 64.

66

Demonstrações, Recursão e Análise de Algoritmo
•37. 10n + 3 . 4n+2 + 5 é divisível por 9.
38. n3 — n é divisível por 3.
39. n3 + 2n é divisível por 3.
40. x" — 1 é divisível por x — 1 para
41. Demonstre o