Lista de Exercicios Matematica Discreta Recursao Torre de Hanoi

MINISTÉRIO DA EDUCAÇÃO SECRETARIA DE EDUCAÇÃO PROFISSIONAL E TECNOLÓGICA INSTITUTO FEDERAL DO NORTE DE MINAS GERAIS IFNMG Criado pela Lei no11892 de 29122008 Campus Pirapora Sistemas de Informação 3º Período Disciplina Matemática Discreta 012023 Profª Renata Fernandes Pereira Lista 5 Recursão Data de Entrega 24072023 Valor 20 pontos Alunoa 1 O jogo de Torre de Hanói tem a seguinte relação de recorrência Utilize o método expandir conjecturar e verificar para encontrar uma solução fechada que dê o número de movimentações necessárias para completar o jogo com n discos 2 Para cada uma das seguintes relações de recorrência calcule os primeiros seis termos da sequência ou seja de a Não é necessário encontrar a fórmula para a b c 3 Resolva cada uma das seguintes relações de recorrência fornecendo uma fórmula explícita para Para cada uma calcule Dica Utilize os teoremas que estabelecem fórmulas para determinar o termo geral da sequência a b c d e Matemática Discreta 1 Tn 2 Tn1 1 Tn 2 2 Tn2 1 1 22 Tn2 21 20 Tn 22 2 Tn3 1 21 20 23 Tn3 22 21 20 Tn 2p Tnp 2p1 2p2 20 se consideramos p n1 tenemos que Tn 2n1 T1 2n2 2n3 20 Tn 2n1 2n2 20 Tn 2n 1 caso base n 1 T1 1 21 1 check mark paso indutivo HI Tk 2k 1 Queremos provar que Tk1 2k1 1 Tk1 2 Tk 1 por HI tenemos Tk1 2 2k 1 1 2k1 2 1 Tk1 2k1 1 check mark 2 a a0 1 a1 2 a0 2 2 2 4 a2 2 a1 2 8 2 10 a3 2 a2 2 20 2 22 a4 2 a3 2 44 2 46 a5 2 a4 2 92 2 94 b a0 1 a1 1 a2 a1 2 a0 1 2 3 a3 a2 2 a1 3 2 5 a4 a3 2 a2 5 6 11 a5 a4 2 a3 11 10 21 c a0 1 a1 1 a2 a0 a1 1 3 a3 a2 a1 1 5 a4 a3 a2 1 9 a5 a4 a3 1 15 3 a an 10 an1 an 102 an2 an 103 an3 an 10p anp Quando n p temos que an 10n a0 an 3 10n a9 3 109 a9 3000000000 b an 4 an1 3 an2 a0 1 a1 2 s1 s2 x2 4 x 3 0 x 3 x 1 0 n1 3 n2 1 c1 2 1 1 3 1 12 c2 2 1 3 3 1 12 an 12 3n 12 1n a9 12 39 12 19 9842 c an 8 an1 15 an2 a0 1 a1 4 s1 s2 x2 8 x 15 0 x 3 x 5 0 n1 3 n2 5 c1 4 1 5 3 5 12 12 c2 4 1 3 3 5 12 12 an 12 3n 12 5n a9 12 39 12 59 a9 986404 2 an 13 an1 1 an 33 an2 1 1 32 an2 31 30 an 32 3 an3 1 31 30 33 an3 32 31 30 an 3p anp 3p1 3p2 30 pn an 3n a0 3n1 3n2 30 an 10 3n 3n 12 an 192 3n 12 ag 192 39 12 186989 4 an 2 an1 2 an2 a0 3 a1 3 s1 s2 x2 2 x 2 0 Δ 22 4 1 2 12 x 2 232 n1 1 3 n2 1 3 c1 3 3 1 31 3 1 3 3323 32 c2 3 3 1 31 3 1 3 3323 32 an 32 1 3n 32 1 3n ag 32 1 39 32 1 39 12720