Lista APA V1

1) O tempo levado para subir a escada é a soma dos tempos levados para subir cada degrau:

T(n) = T(n-1) + T(n-2) + T(n-3) + ...+ T(1)
T(n) = T(n-1) + T(n-2) + T(n-3) + ...+ 1

Mas se analisarmos o T(n-1) percebemos que ele é igual ao restante do somatório:
T(n-1) = T(n-2) + T(n-3) + ...+ 1

Substituindo temos que:
T(n) = T(n-1) + T(n-1)
T(n) = 2T(n-1)

Sendo assim, as equações de recorrência são:
T(1)=1
T(n)=2T(n-1)

Resolvendo a equação de recorrência, temos que:
T(n)=2T(n-1)
= 2(2T(n-1-1)) = 2²T(n-2) = 2²(2T(n-2-1)) = 2³T(n-3)
Após k passos, temos:
T(n)=2kT(n-k)

Supondo n-k=1, temos k=n-1
T(n)=2n-1.T(1) => 2n-1.1
T(n)=2n-1 e O(2n)

Outra forma de entender o problema é enxergar a escada como um vetor de n posições, em que cada degrau(posição) possui duas opções de valores: 1 para quando o degrau foi pisado e 0 para quando o degrau foi pulado. O último degrau (última posição do vetor) sempre será 1 pois é o destino, é obrigatório que seja o último passo.
[1 ou 0] [1 ou 0] [1 ou 0] ... [1]
Como são n-1 posições e temos 2 opções para cada, temos que todas as combinações diferentes podem ser representadas pela expressão 2n-1.
Mas dessa forma estamos fazendo o processo inverso até chegar nas equações de recorrência.

2)
T(1)=1
T(n)=3T(n-1)+2, para todo n>1

T(n)=3T(n-1)+2
= 3(3T(n-1-1)+2)+2
=3²T(n-2)+2.3+2
=3²(3T(n-2-1)+2)+2.3+2
=3³T(n-3)+3.3²+2.3+2
=3³(3T(n-3-1)+2)+2.3²+2.3+2
=34(n-4)+2.3³+2.3²+2.3+2
...
Após k passos, temos:
T(n)= 3kT(n-k)+2.3k-1+...+2.3²+2.3¹+2.3°

Ao final do processo esperamos obter:
Em T(n-k), n-k = 1 temos k=n-1, logo:

T(n) = 3(n-1)T(1) +2.3(n-2)+...+2.3²+2.3¹+2.3°
T(n) = 3(n-1)T(1) + ∑i=0 n-2 2.3i => 3(n-1) + 2 ∑i=0n-2 3i

T(n) = 3n-1 + 2((3n-1 - 1/(3 - 1)*) = 3n-1 + 3n-1 - 1
T(n) = 2.3n-1 - 1 => O(3n)

*Obs.: Para resolver o somatório usamos a seguinte fórmula:

S = ∑i=0 n ai = 1 + a + a2 + ... + an

Multiplicamos por (a-1) nos dois lados:

(a-1) S = 1 + a + a2 + ... + an .(a-1)

(a-1) S = a + a2 +