SOLUÇÃO DA AP2-2018-1

Prévia do material em texto

SOLUÇÃO DA AP2 – 2018/1 – MD 
 
1. (8 5 1 8 (mod 9)) (6 7 (mod 11)) ) (mod 10) ) 
8 x 5 (mod 9) = 4 + 1 (mod 9) = 5 – 8 (mod 9) = -3 (mod 9) = 6. 
 6 x 7-1 ( mod 11) = 6 x 8 (mod 11) = 4. 
4 x 6 (mod 10) = 24 (mod 10) = 4. 
x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x 
2. 
 6 1 2 2 
611 91 65 26 13 
65 26 13 0 
Logo, mdc(611, 91) = 13 
x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x 
 
3. x ≡ 6 (mod 7) 
x ≡ 9 (mod 12) 
x = 6 + 7k. Substituindo esse valor de x na segunda equação, temos: 
6 + 7k = 9 (12) ∴ 7k = 9 – 6 (11) ∴ 7k = 3 (12) ∴ 7 7-1 k = 3 7-1 (12) ∴ 7 x7 k= 3x7(12) 
∴ 49 k = 21 (12) ∴ k = 9 (12). 
x = 6 + 7k ∴ x = 6 + 7 (9 + 12j) = 6 + 63 + 84j ∴ x ≡ 69 (mod 84). 
 
Outra forma de resolução: 
 A M M* M*-1 AMM*-1 
X = 6 (mod 7) 6 12 5 3 216 
X = 9 (mod 12) 9 7 7 7 441 
 657 
657 (mod 84)  x ≡ 69 (mod 84) 
 
x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x 
 
4. 
6
)12)(1(
...21 222
++=+++ nnnn 
Provar P(1): 12 = (1(1+1)(2x1+1))/6 ∴ 1 = 1. 
Supor a hipótese: 
6
)12)(1(
...21 222
++=+++ nnnn 
Provar P(n +1) 
6
)32)(2)(1(
6
)1)1(2)(11)(1(
)1(...21 2222
+++=+++++=+++++ nnnnnnnn 
hipóteseporn
nnn
nn 22222 )1(
6
)12)(1(
)1(...21 ++++=+++++
 
=++++=++++=++++
6
))1(6)12()(1(
6
)1(6)12)(1(
)1(
6
)12)(1( 22 nnnnnnnn
n
nnn
 
=++++=+++++=++++
6
)3264)(1(
6
)6242)(1(
6
)662)(1( 222 nnnnnnnnnnnnn
 
6
)2)(32)(1(
6
))32()32(2)(1( nnnnnnn +++=++++ c.q.d. 
 
 
5. 
nn 27 − é divisível por 5 
Provar P(1): .5,52727 11 pordivisíveléque=−=− 
Supor a hipótese: nnnnnn kkeirokk 257527.int,527 +=∴=−=− 
Provar P(n+1): 
.,22)25(7227727 11 hipótesepork nnnnnn ⋅−+=⋅−⋅=− ++ 
)27(5253522273522)25(7 nnnnnn kkkk +=⋅+=⋅−⋅+=⋅−+ . 
P(n+1) é múltiplo de 5, logo, é divisível por 5. 
x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x 
6. S = 2, 9, 25, 59, 129, 271, ... 
 
 
S(1) = 2 
S(2) = 9 = 2 + 7 = 2 + 2 + 5 
S(3) = 25 = 9 + 16 = 9 + 9 + 7 
S(4) = 59 = 25 + 34 = 25 + 25 + 9 
S(5) = 129 = 59 + 70 = 59+59 + 11 
 
Definição recorrente: S(1) = 2 
 S(n) = 2S(n – 1) + 2n + 1, n >= 2 
x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x 
 
7. S(1) = 1 
S(n) = 2S(n – 1) + 2n 
Fazendo c = 1 e g(n) = 2n , temos a recorrência no formato cS(n-1) + g(n) 
Aplicando a fórmula 
=
−− +=
n
i
inn igcScnS
2
1 )()1()( 
nnnnnnn
nS 22...22222212)(
4433221 ⋅+++⋅+⋅+⋅= −−−−− 
nnnnn
nS 2...2222)(
1 +++++= − 
nn
nnS 2)1(2)(
1 −+= − , que é a forma fechada. 
 
Pelo método de expandir: 
n
nSnS 2)1(2)( +−= 
nnnnn
nSnSnSnS 2.2)2(222.2)2(22)2)2(2(2)(
2121 +−=++−=++−= −− 
nnnnn
nSnSnSnS 2.3)3(222.2)1(22)2.2)3(2(2)(
3312 +−=++−=++−= − 
Conjectura: 
nK
kknSnS 2.)(2)( +−= , até n – k = 1, ou k = n – 1. 
nnnnnn
nnSnnnSnS 2).1(22).1()1(22).1()1(2)(
111 −+=−+=−++−= −−− 
Verificar 
P(1): 21-1 + (1 – 1) . 21 =20 + 0 = 1 
Supor: S(n) = 2n-1 + (n – 1).2n 
P(n+1): 
S(n+1) = 2n+1-1 + (n + 1 – 1).2n+1 = 2n + n.2n+1 
Função S(n) 
Se n = 1 então 
 Retorne 2 
Senão 
 Retorne 2S(n – 1) + 2n + 1 
 
S(1) 2 2 
S(2) 2S(1)+2.2+1 9 
S(3) 2S(2)+2.3+1 25 
S(4) 2S(3)+2.4+1 59 
S(5) 2S(4)+2.5+1 129 
 
S(n+1) = 2S(n+1 – 1) + 2 n+1 ( da recorrência) 
= 2S(n) + 2 n+1 
= 2( 2n-1 + (n – 1).2n ) + 2 n+1, por hipótese. 
= 2.2n-1 + 2(n – 1).2n + 2 n+1 
= 2n + 2.n.2n – 2.2n + 2 n+1 
= 2n + n2n+1 – 2n+1 + 2 n+1 
= 2n + n2n+1 , c. q. d. 
 
x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x 
 
7 – Alternativa 
S(1) = 1200 
S(2) = 1800 = 1200 + 600 
S(3) = 2700 = 1800 + 900 
S(4) = 4050 = 2700 + 1350 
Logo, pode-se concluir que S(n) = S(n – 1) + S(n – 1) / 2 = 3/2S(n – 1) 
 
Pela fórmula: c = 3/2, g(n) = 0 
S(n) = (3/2)n – 1. 1200 + i=2,n c
n-i . g(i) = = (3/2)n – 1. 1200 + 0 . i=2,n c
n-i 
S(n) = 1200(3/2)n – 1 
 
Pelo método de expandir: 
S(n) = 3/2S(n – 1) 
S(n) = 3/2 . 3/2S(n -2) = 9/4 S(n - 1) 
S(n) = 3/2 . 9/4 S(n -3) = 27/8S(n – 3) = 33/23S(n – 3) 
Conjectura: 
S(n) = 3k/2kS(n – k), até n – k = 1 ou k = n – 1. 
S(n) = 3n -1 / 2n - 1 S(n – (n – 1)) 
S(n) = 3n -1 / 2n - 1 S(1) 
S(n) = 1200(3/2)n – 1 
Verificar 
Provar p(1) 
1200(3/2) 1 – 1 = 1200 
Supor a hipótese S(n) = 1200(3/2)n – 1 
Provar P(n+1): P(n+1) = 1200(3/2)n – 1+1 = 1200(3/2)n 
S(n + 1) = 3/2S(n – 1 + 1) = 3/2S(n) = 3/2(1200(3/2)n – 1) = 1200(3/2)n