Question

70 pontosssssss, mas só se responder certo e até 11:40 de hoje

Answer 1

Resposta:

a)  f(n) = 2f(n-1) + 1 => f(3)=2(f2)+1

Como f(2)=2(f1)+1 e f(1)=1 temos que f(2)=3

logo f(3)=2.3+1=7

b) Por indução:

f(n + 1) = 2f(n)+1

assim  

$f(n+1)=2(2^{2}-1)+1 => f(n+1)=2.2^{2}-2+1=2^{n+1}-1$

Pelo Princípio de Indução Finita:

$f(n)=2^{n} -1$ para todo número n natural e maior que 1.

Explicação passo a passo:

Vamos considerar uma torre com n discos numerando como 1 o menor disco  e n o maior disco (1, 2, 3, ..., n). Para remover o disco n é preciso tirar todos  de cima, ou seja, tirar todos os n−1 discos que estão acima dele colocando-os em uma das hastes, feito isso, mova o disco n para a haste restante. Agora  mova de acordo com as regras os n− 1 para a haste que se encontra o disco  n. Observe que você move os n−1 discos duas vezes e o disco n apenas  uma. De modo matemático, seja f(n) o número mínimo de movimentos para  resolver uma Torre de Hanói com n discos, f(n−1) é o número mínimo de  movimentos para n−1 discos, então temos:

f(n) = f(n − 1) + 1 + f(n − 1)  => f(n) = 2f(n − 1) + 1