Seja a_n o número de maneiras de se cobrir uma caixa 1 * n com retângulos 1 x 1,1 x 2 e 1 x 3. Obtenha uma relação de recorrência para a_n.

Passo 1

Beleza, vamos lá! A gente tem uma caixa que é de tamanho 1 * n e queremos cobri-la usando retângulos que são , e 1 x 3. A questão está pedindo para a gente encontrar uma relação de recorrência para a_n, que é o número de maneiras de fazer essa cobertura. Vamos precisar usar conceitos de recorrência e combinatória para resolver isso.

Passo 2

Primeiro, vamos entender o que é uma relação de recorrência. É tipo uma fórmula que relaciona o termo atual de uma sequência com os anteriores. No nosso caso, queremos expressar a_n em função de , e .

Passo 3

Agora, imagina que estamos começando a cobrir a caixa de 1 * n. A primeira peça que colocamos na caixa pode ser de três tamanhos diferentes:
  1. Retângulo : Se colocarmos esse primeiro retângulo, ele ocupa uma posição, e sobra uma caixa de . O número de maneiras de cobrir essa parte restante é .
  2. Retângulo : Se usarmos esse retângulo primeiro, ele ocupa duas posições, deixando uma caixa de . As maneiras de cobrir essa parte são .
  3. Retângulo 1 x 3: Colocando esse primeiro, ele ocupa três posições, sobrando uma caixa de . As maneiras de cobrir essa parte são .

Passo 4

Como qualquer uma dessas três opções pode ser a primeira peça que colocamos, o total de maneiras de cobrir a caixa de 1 * n é a soma das maneiras de cada caso. Então, a relação de recorrência fica:

Passo 5

Essa fórmula nos diz que, para encontrar o número de maneiras de cobrir uma caixa de 1 * n, a gente soma as maneiras de cobrir as caixas de tamanhos menores: , e . É uma forma eficiente de resolver o problema usando passos menores.

Resposta

A relação de recorrência para a_n é:

Exercícios relacionados