Prova combinatória para uma identidade Fibonacci

Question

$$f_{n+2} + f_{n-2} = 3f_n \text{ for n} \ge 1 $$

Estou tentando entender a prova combinatória que vejo no livro que estou lendo para a identidade acima. Aqui$f_n$ representa o número de maneiras de colocar uma placa retangular de tamanho $1 \times n$ com ladrilhos de tamanho $1 \times 1$ e $1 \times 2$. No livro, o autor estabelece uma correspondência de 1 para 3 entre o conjunto de$1 \times n$ coisas e o conjunto de $1 \times (n-2)$ telha e $1 \times (n+2)$ tilings, doravante referidos como Conjunto 1 e Conjunto 2, respectivamente, de modo que para cada objeto no Conjunto 1, podemos criar três objetos exclusivos no Conjunto 2.

Conjunto 1: Tilings de um $1 \times n$ borda

Conjunto 2: Tilings de um $1 \times (n+2)$ placa ou um $1 \times (n-2)$ borda.

O autor então explica a correspondência 1 para 3 como abaixo:

O primeiro ladrilho é um $1 \times (n+2)$ ladrilho criado anexando um ladrilho de tamanho $1 \times 2$ ao $1 \times n$ revestimento

O segundo ladrilho é um $1 \times (n+2)$ ladrilho criado ao anexar dois ladrilhos de tamanho $1 \times 1$ ao $1 \times n$ revestimento

Para a terceira parte, o autor surge com algo que não consigo entender. Eles dizem que se o$1 \times n$ lado a lado termina com um

Eu) $1 \times 2$ telha, em seguida, remova o $1 \times 2$ lado a lado para criar um $1 \times (n-2)$ revestimento.

ii) $1 \times 1$ ladrilho, em seguida, insira um $1 \times 2$ telha antes da última $1 \times 1$ telha para criar um $1 \times (n+2)$ revestimento.

Então, para provar a correspondência de 1 para 3, eles provam que cada ladrilho de tamanho $1 \times (n+2)$ ou tamanho $1 \times (n-2)$ é criado exatamente uma vez a partir de algum $1 \times n$revestimento. Eles raciocinam da seguinte maneira:

Para um dado $1 \times (n+2)$ lado a lado, podemos obter o $1 \times n$ lado a lado que o cria examinando seu final e removendo

i) o último $1 \times 2$ telha (se terminar com um $1 \times 2$ telha)

ii) os dois últimos $1 \times 1$ peças (se terminar com dois $1 \times 1$ azulejos)

iii) o último $1 \times 2$ telha (se terminar com um $1 \times 1$ telha precedida por um $1 \times 2$ telha)

E por um dado $1 \times (n-2)$ lado a lado, podemos simplesmente anexar um bloco de tamanho $1 \times 2$ para o $1 \times n$ lado a lado que o cria.

E eles concluem que, como o Conjunto 2 é três vezes o tamanho do Conjunto 1, a identidade segue.

Embora eu entenda tudo isso, não consigo entender como um bloco de tamanho $1 \times n$ pode ser formado exatamente de uma maneira a partir de um mosaico de tamanho $1 \times (n-2)$, já que eu poderia anexar um bloco de tamanho $1 \times 2$ ou duas coisas do tamanho $1 \times 1$ ao $1 \times (n-2)$ lado a lado para criar um $1 \times n$ revestimento.

Além disso, também poderia inserir um bloco de tamanho $1 \times 1$ para um $1 \times n$ lado a lado, para formar um $1 \times (n+1)$ lado a lado, se a placa de $1 \times n$ terminou com um bloco de $1 \times 2$. O que significaria$f_{n+2} + f_{n+1} = 3f_n$. Mas eu sei que isso é falso. Só não sei por que meu raciocínio está incorreto.

Lamento que este seja longo. Eu apreciaria quaisquer explicações para as duas preocupações acima.

Answer 1

A alegação não é que um $1\times n$ os ladrilhos podem ser formados apenas de uma maneira a partir de um $1\times(n-2)$revestimento. Nesse ponto, você recebeu um procedimento muito específico que produz três$1\times(n+2)$ ou $1\times(n-2)$ coisas de cada $1\times n$ lado a lado, e a alegação é que há exatamente um $1\times n$ ladrilhos que poderiam ter produzido qualquer $1\times(n-2)$lado a lado por esse procedimento . O procedimento produz um$1\times(n-2)$lado a lado apenas removendo um$1\times 2$ ladrilho do final de um $1\times n$ lado a lado, nunca removendo dois $1\times 1$ telhas, então o único $1\times n$ telha da qual um dado $1\times(n-2)$ o que poderia ter resultado é aquele que você obtém quando anexa um $1\times 2$ telha.

Toda a segunda parte do argumento mostra que cada $1\times(n-2)$ ou $1\times(n+2)$tiling é o resultado da aplicação do procedimento da primeira parte do argumento a um único $1\times n$revestimento. Ou seja, se você receber um$1\times(n-2)$ ou $1\times(n+2)$ lado a lado, você sempre pode trabalhar para trás para descobrir o único $1\times n$lado a lado que dá origem a ele quando você aplica o procedimento descrito na primeira parte do argumento. Isso é o que mostra que o procedimento realmente define um$1$-para-$3$ correspondência entre Set $1$ E definir $2$: dado um $1\times n$ lado a lado, há uma regra que especifica exatamente $3$ membros correspondentes de Set $2$, e dado qualquer membro de Set $2$, há uma regra que informa o membro único de Set $1$ a que corresponde.