Questão 66587

Em uma disciplina de Lógica e Matemática Discreta para licenciandos em Computação, o professor quer que os alunos compreendam a Relação de Recorrência como uma ferramenta poderosa para modelar problemas e analisar a complexidade de algoritmos recursivos. Ele percebe que os alunos conseguem resolver recorrências simples por substituição, mas não entendem como modelar um problema do mundo real com elas. Para contextualizar, ele apresenta o clássico problema da Torre de Hanói e um trecho de 'Matemática Discreta e Suas Aplicações' de Kenneth Rosen: "Muitos problemas podem ser resolvidos usando uma abordagem recursiva, onde a solução para um problema de tamanho $n$ é expressa em termos da solução para problemas menores. Uma relação de recorrência é uma equação que expressa o termo $a_n$ em termos de um ou mais dos termos anteriores da sequência. Analisar a complexidade de um algoritmo recursivo muitas vezes se traduz em resolver a relação de recorrência que descreve o número de operações que ele executa." O problema da Torre de Hanói com $n$ discos pode ser resolvido recursivamente da seguinte forma: 1. Mover $n-1$ discos da estaca de origem para a estaca auxiliar (requer $T(n-1)$ movimentos). 2. Mover o disco maior da origem para o destino (1 movimento). 3. Mover os $n-1$ discos da estaca auxiliar para a estaca de destino (requer $T(n-1)$ movimentos). O professor então pede aos alunos que, com base nessa descrição, modelem o número de movimentos $T(n)$ como uma relação de recorrência e identifiquem a condição inicial.

Qual é a relação de recorrência correta e a condição inicial que modelam o problema da Torre de Hanói?