Flashcard FC628398
Qual é a fórmula fechada da recorrência T(n)=2T(n-1)+1 com T(1)=1?
Sequências de Números, Figuras, Letras e Palavras
NC UFPR (FUNPAR) · 2015
Qual é a fórmula fechada da recorrência T(n)=2T(n-1)+1 com T(1)=1?
Mostrar resposta e comentário
Resposta
T(n)=2^n-1Explicação:
Prova por indução: base \(T(1)=1=2^1-1\). Suponha \(T(k)=2^k-1\), então \(T(k+1)=2T(k)+1=2(2^k-1)+1=2^{k+1}-1\), portanto vale para todo \(n\).
Exemplo:
\(T(5)=2^5-1=32-1=31\), equivalente à expansão \(T(5)=2^4T(1)+(2^4-1)=16\cdot1+15=31\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/626417
Conteúdo do catálogo FC Concursos · Atualizado em