Simulacro Nacional 2022 Politecnico - Nivel 3 Problema 2

[Fedex]

Decimos que una palabra es un palíndromo si se lee igual en ambos sentidos. Construimos una secuencia de palabras de la siguiente manera: $P_0=a$, $P_1=b$ y para $n \geq 2$ la palabra $P_n$ resulta de escribir la palabra $P_{n-2}$ seguida de $P_{n-1}$.
Demostrar que para $n\geq 1$ la palabra $P_1P_2\cdots P_{n-1}P_n$ es un palíndromo.

[Fedex]

Spoiler: mostrar

Dada una palabra $P$ definimos $\overline{P}$ como la palabra $P$ leída al revés. Entonces las palabras palíndromo son aquellas que satisfacen que $\overline{P} = P$.
Notemos las siguientes cosas:

• $\overline{\overline{A}} = A$ ya que si damos vuelta una palabra $2$ veces tenemos la palabra original.

• $\overline{AB} = \overline{B} \; \overline{A}$ ya que si leemos al revés una palabra compuesta leemos primero la palabra del final al revés y luego la del principio. En general, se da que $\overline{A_1A_2 \cdots A_{i-1} A_i} = \overline{A_i} \; \overline{A_{i-1}} \; \cdots \; \overline{A_2} \; \overline{A_1}$

Primero verificamos lo pedido para $n = 0,1,2$. La palabra que se forma con $n = 0$ es vacía por lo que trivialmente esto es cierto. La palabra $P_1 = b$ también es palíndromo. Finalmente la palabra $P_2 = ab$ luego $P_1P_2 = bab$ que es palíndromo.

Ahora vamos a demostrar lo pedido por inducción: Supongamos que el enunciado es cierto para $n \geq 0$ y para $n+2 \geq 2$ luego $P_1P_2\cdots P_n$ y $P_1P_2\cdots P_{n+2}$ son palíndromos, veremos que esto es cierto para $n+3$.
Notar que:
$$\overline{P_1\cdots P_{n+3}} = \overline{P_{n+3}} \; \overline{P_1\cdots P_n P_{n+1}P_{n+2}} = \overline{P_{n+3}} P_1 \cdots P_n P_{n+1} P_{n+2} = \overline{P_{n+2}} \; \overline{P_{n+1}}P_1\cdots P_n P_{n+1}P_{n+2} $$
Donde si leemos al revés lo ultimo tenemos que:

$$\overline{\overline{P_{n+2}} \; \overline{P_{n+1}} P_1\cdots P_n P_{n+1}P_{n+2}} = \overline{P_{n+2}} \; \overline{P_{n+1}} \; \overline{P_1\cdots P_n} \; \overline{\overline{P_{n+1}}} \; \overline{\overline{P_{n+2}}}
= \overline{P_{n+2}} \; \overline{P_{n+1}} \; \overline{P_1\cdots P_n} P_{n+1} P_{n+2}
= \overline{P_{n+2}} \; \overline{P_{n+1}} \; P_1\cdots P_n P_{n+1} P_{n+2}$$

Por lo que si leemos al revés esta palabra, es la misma. Donde concluimos que $\overline{P_1\cdots P_{n+3}}$ es un palíndromo, es decir, $P_1\cdots P_{n+3}$ es un palíndromo, como queríamos demostrar.