[R_Gauss]

Hola,

tengo este ejercicio sobre recurrencia que no logro ver cómo dar respuesta:

Considere la secesión \( \{P_n\}_{n≥0} \) definida por \( P_n = 2P_{n−1} + P_{n−2} \) para \( n ≥ 2 \), con los valores iniciales \( P_0 = 0 \) y \( P_1 = 1 \).

Sea \( Q_n \) el número de formas de teselar una cinta de tamaño \( 2 × n \) \(  (n ≥ 1) \) con las siguientes tres baldosas:
(Adjunto imagen).



Demuestre que \( Q_n = P_{n+1} \) para todo \( n ≥ 1 \).

Agradezco sus colaboraciones,

De paso: ¿Algún texto o ejercicios similares al propuesto?

Saludos,

[Luis Fuentes]

Hola

tengo este ejercicio sobre recurrencia que no logro ver cómo dar respuesta:

Considere la secesión \( \{P_n\}_{n≥0} \) definida por \( P_n = 2P_{n−1} + P_{n−2} \) para \( n ≥ 2 \), con los valores iniciales \( P_0 = 0 \) y \( P_1 = 1 \).

Sea \( Q_n \) el número de formas de teselar una cinta de tamaño \( 2 × n \) \(  (n ≥ 1) \) con las siguientes tres baldosas:
(Adjunto imagen).



Demuestre que \( Q_n = P_{n+1} \) para todo \( n ≥ 1 \).

Agradezco sus colaboraciones,

De paso: ¿Algún texto o ejercicios similares al propuesto?

Fíjate que podemos empezar a teselar con dos piezas 1x2 (una sobre otra) o bien con una pieza 1x2 azul o blanca.

En el primer caso nos quedaría por teselar una cinta de longitud \( n-2 \); en el otro cintas de longitud \( n-1 \). De ahí:

\( Q(n)=Q(n-2)+2Q(n-1) \)

Saludos.

[geómetracat]

No sé si estoy despistado pero, estando totalmente de acuerdo con la solución de Luis, no veo que \( P_1=1 \). Parece que haya dos formas de teselar una pieza \( 2 \times 1 \): con la pieza blanca o con la pieza azul.

[Luis Fuentes]

Hola

No sé si estoy despistado pero, estando totalmente de acuerdo con la solución de Luis, no veo que \( P_1=1 \). Parece que haya dos formas de teselar una pieza \( 2 \times 1 \): con la pieza blanca o con la pieza azul.

Fíjate que:

Demuestre que \( Q_n = P_{n+1} \) para todo \( n ≥ 1 \).

Es decir el número de formas de teselar una pieza de \( 2\times 1 \) no es \( P_1 \) sino:

\( Q_1=P_2=2P_1+P_0=2 \).

No se muy bien porque el ejercicio usa esa doble notación con dos sucesiones... 

Saludos.

[geómetracat]

¡Ah! Tienes toda la razón, eso me pasa por no leer bien.
¡Gracias!

[R_Gauss]

Hola, Gracias por la respuesta

Demuestre que \( Q_n = P_{n+1} \) para todo \( n ≥ 1 \).

..............

Fíjate que podemos empezar a teselar con dos piezas 1x2 (una sobre otra) o bien con una pieza 1x2 azul o blanca.

En el primer caso nos quedaría por teselar una cinta de longitud \( n-2 \); en el otro cintas de longitud \( n-1 \). De ahí:

\( Q(n)=Q(n-2)+2Q(n-1) \)

Saludos.

¿Debo demostrar que: \( Q(n)=Q(n-2)+2Q(n-1) \)] y luego suponer que se cumple para un \( n \) y demuestro para un \( n+1 \)?

Estoy confundido con la notación.


¿Qué debo demostrar?

Saludos,

[Luis Fuentes]

Hola

¿Debo demostrar que: \( Q(n)=Q(n-2)+2Q(n-1) \)] y luego suponer que se cumple para un \( n \) y demuestro para un \( n+1 \)?

No. Esa relación ya la he justificado.

Lo que tienes que probar que si ahora tomas:

\( P_n=Q_{n-1}  \) (que equivale a \( Q_n=P_{n+1} \))

entonces \( P_n \) cumple lo que dice el enunciado es decir que:

\( P_n=P_{n-2}+2P_{n-1} \)
\( P_0=0 \) y \( P_1=1 \)

Para ello ten en cuenta que trivialmente \( Q_1=2 \) y \( Q_2=5 \)

Saludos.

[R_Gauss]

Hola,

\( P_n=Q_{n-1}  \) (que equivale a \( Q_n=P_{n+1} \))

entonces \( P_n \) cumple lo que dice el enunciado es decir que:

\( P_n=P_{n-2}+2P_{n-1} \)
\( P_0=0 \) y \( P_1=1 \)

Para ello ten en cuenta que trivialmente \( Q_1=2 \) y \( Q_2=5 \)

Saludos.

¿Pero no es necesario aplicar inducción matemática?
Es decir,
\( P_4=Q_3=P_2+2P_3=2+10=12 \) Si seguimos de esa forma, llegaremos a la igualdad:

\( P_n=Q_{n-1}=P_{n-2}+2P_{n-1} \)

¿La inducción nos sirve para demostrar ese paso que se da?

Saludos,

[Luis Fuentes]

Hola

¿Pero no es necesario aplicar inducción matemática?
Es decir,
\( P_4=Q_3=P_2+2P_3=2+10=12 \) Si seguimos de esa forma, llegaremos a la igualdad:

\( P_n=Q_{n-1}=P_{n-2}+2P_{n-1} \)

¿La inducción nos sirve para demostrar ese paso que se da?

Buff. depende. A ver como lo explico.

En realidad lo primero que tendrías que probar por inducción es que una relación de recurrencia lineal del tipo:

\( a_n=b_1a_{n-1}+b_2a_{n-2}+\ldots+b_ka_{n-k} \)

define de manera inequívoca una sucesión fijados \( k \) valores \( a_1,a_2,\ldots,a_k \) de la misma.

Pero esto suele demostrarse cuando se desarrolla la teoría de ecuaciones en recurrencia.

Una vez demostrado para ver que dos sucesiones definidas por recurrencia coinciden basta ver que son la misma relación de recurrencia y que coinciden en \( k \) valores (en tu caso en dos valores), que es lo que te he sugerido.

Saludos.

[R_Gauss]

Hola,

Si ya no tengo tres baldosas sino cuatro, ¿la relación para \( Q_n \) se mantiene? Es decir, si tengo:


¿Entonces la recurrencia cambia? ¿Cómo podría encontrar la relación de recurrencia para \( Q_n \)

Saludos,