Question

Existe uma escada com N degraus. Você pode escolher entre descer 1, 2, ou 3 degraus por vez a cada movimento. De quantas maneiras diferentes você poderia descer essa escada com N degraus?

Suponhamos que sejam 5 degraus, a resposta é ''13'', me expliquem o pq desse resultado por favor.

Answer 1

Se existem 5 degraus, então existem 13 maneiras de descer a escada.

Primeiramente, observe que não é possível descer somente utilizando 2 degraus nem 3 degraus.

É possível descer a escada utilizando 1 degrau por vez: 1 - 1 - 1 - 1 - 1.

Utilizando 1 degrau e 2 degraus, temos as seguintes possibilidades:

2 - 2 - 1

2 - 1 - 2

1 - 2 - 2

2 - 1 - 1 - 1

1 - 2 - 1 - 1

1 - 1 - 2 - 1

1 - 1 - 1 - 2.

Utilizando 1 degrau e 3 degraus, temos as possibilidades:

3 - 1 - 1

1 - 3 - 1

1 - 1 - 3.

Utilizando 2 degraus e 3 degraus, temos as possibilidades:

3 - 2

2 - 3.

Portanto, no total, existem 1 + 7 + 3 + 2 = 13 maneiras de descer a escada.