FTC Lista05

Prévia do material em texto

Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Engenharia de Computação
Fundamentos de Teoria da Computação
Prof. Rodrigo Yoshikawa Oeiras
Lista de Exercícios 05: Indução
1. 2+6+10+...+(4n-2)=2n2
2. 2+4+6+...+2n=n(n+1)
3. 1+5+9+...+(4n-3)=n(2n-1)
4. 1+3+6+...+n(n+1)/2 = n(n+1)(n+2)/6
5. 4+10+16+...+(6n-2) = n(3n+1)
6. 5+10+15+...+5n=5n(n+1)/2
7. 12+22+...+n2=n(n+1)(2n+1)/6
8. 13+23+...+n3=n2(n+1)2/4
9. 1⋅1!+2⋅2!+3⋅3 !+...+n⋅n!=(n+1)!−1 , onde n! É o produto dos inteiros 
positivos de 1 a n.
10. Uma progressão geométrica é uma sequência de termos com um termo 
inicial “a” tal que cada termo a seguir é obtido multiplicando-se o termo anterior 
por uma mesma razão “r”. Prove a fórmula para a soma dos n primeiros termos 
de uma progressão geométrica (n≥1).
a+ar+ar 2+...+a rn−1=a−ar
n
1−r
11. Uma progressão aritmética é uma sequência de termos com um termo 
inicial “a” tal que cada termo a seguir é obtido somando-se uma mesma parcela 
“d” ao termo anterior. Prove a fórmula para a soma dos n primeiros termos de 
uma progressão aritmética (n≥1).
a+(a+d)+(a+2d)+...+[a+(n−1)d ]= n
2
[2a+(n−1)d ]
12. Prove n² ≥ 2n+3 para n≥3.
13. Prove que n² > n + 1 para n ≥ 2.
14. Prove que n² > 5n + 10 para n > 6.
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Engenharia de Computação
15. Prove que 2n > n² para n ≥ 5.
16. Prove que n! > n² para n ≥ 4.
17. Prove que n! > 3n para n ≥ 7.
18. Prove que n! < nn para n ≥ 2.
19. Prove que a proposição é verdadeira para todo o inteiro positivo n:
a) 32n + 7 é divisível por 8.
b) 7n – 2n é divisível por 5.
c) 13n – 6n é divisível por 7.
d) 25n+1 + 5n+2 é divisível por 27.
e) n³ + 2n é divisível por 3.
20. Prove que qualquer quantia em selos maior ou igual a 2 centavos pode 
ser obtida usando-se apenas selos de 2 e 3 centavos.
21. Prove que qualquer quantia em selos maior ou igual a 64 centavos pode 
ser obtida usando-se apenas selos de 5 e 17 centavos.
22. O caixa automático do seu banco usa apenas notas de R$ 20,00 e de R$ 
50,00 para dar dinheiro. Prove que você pode obter, além de R$ 20,00, 
qualquer quantia múltipla de R$ 10,00 que seja maior ou igual a R$ 40,00.
23. Considerando os números de Fibonacci, prove:
a)F(n+3) = 2F(n+1)+F(n) para n ≥ 1.
b) F(n+6) = 4F(n+3)+F(n) para n ≥ 1.
c) F(1) + F(3) + … + F(2n-1) = F(2n) para n ≥ 1.
d) [F(1)]² + [F(2)]² + … + [F(n)]² = F(n) F(n+1) para n ≥ 1.