Ad2 - fac

AD2 - Fundamentos de Algoritmos para Computação

1. (1.0) Usando o Teorema das colunas calcule a seguinte soma: S = 10 · 11 · 12 + 11 · 12 · 13 + 12 · 13 · 14 + · · · 50 · 51 · 52 Resposta: Notemos que: 10 · 11 · 12 + 11 · 12 · 13 + · · · + 50 · 51 · 52 = (1 · 2 · 3 + 2 · 3 · 4 + · · · + 50 · 51 · 52) − (1 · 2 · 3 + 2 · 3 · 4 + · · · + 9 · 10 · 11) Isto ´, e
50 50 9

k(k + 1)(k + 2) = k=10 k=1

k(k + 1)(k + 2) − k=1 k(k + 1)(k + 2)

Pelo desenvolvimento do exemplo 4, na aula 13, slide n´ mero 29, temos que: u
50 4 k(k + 1)(k + 2) = 6 · C53 k=1

Com racioc´ ınio an´logo, temos que: a
9 4 k(k + 1)(k + 2) = 6 · C12 k=1

Portanto,
50 4 4 4 4 k(k + 1)(k + 2) = 6 · C53 − 6 · C12 = 6(C53 − C12 ) k=10

Obs.: Na avalia¸˜o a distˆncia deve ser colocada a explica¸˜on de 50 k(k+1)(k+ ca a ca k=1 4 4 a 2) = 6·C53 e 9 k(k +1)(k +2) = 6·C12 . Para acompanh´-las, consulte o material k=1 das aulas. 2. (1.5) Usando o Teorema do binˆmio de Newton calcule: o n kC(n, k)(−3)k k=0 Resposta: n n

k · C(n, k) · (−3)k = k=0 k=0

k·

n! · (−3)k = k!(n − k)!

n

= 0 + k=0 k=1

k·

n(n − 1)! (−3)k = k · (k − 1)!(n − k)!

n

k=1

n(n − 1)! (−3)k (k − 1)!(n − k)!

Fazendo mudan¸a de vari´vel, k −1 = j, temos que k = j +1 e para k = n, j = n−1. c a Da´ segue: ı, n k=1 n−1

n(n − 1)! (−3)k = (k − 1)!(n − k)!

n−1

j=0

n(n − 1)! (−3)j+1 = j!(n − j − 1)! n−1 =n j=0 (n − 1)! (−3)j (−3) = (−3)n C(n − 1, j)(−3)j 1n−1−j j!((n − 1) − j)! j=0

Pelo Teorema Binomial, temos: n−1 (−3)n j=0 1n−1−j (−3)j C(n − 1, j) = (−3)n(1 − 3)n−1 = n(−3)(−2)n−1

3. (1.5) Uma pessoa deve pintar uma sequˆncia de n blocos, n ≥ 1, com as cores e vermelha, azul e branca, cada bloco com uma unica cor tal que blocos consecutivos ´ e n˜o podem ser pintados de branco. Encontre uma rela¸˜o de recorrˆncia para o a ca n´ mero de sequˆncias poss´ u e ıveis (an = o n´ mero de sequˆncias de n blocos pintados u e com as cores vermelha, azul e branca