Un amigo mío me enseñó la siguiente pregunta. Él dijo que él creó a la pregunta por sí mismo y conjeturó la respuesta, pero no podía demostrarlo. A pesar de que he tratado de resolver la cuestión, he estado en la dificultad.
La pregunta es acerca de la viruta de los rectángulos. (El siguiente es un ejemplo, cuando nos montón de trece $1\times 2$ rectángulos.)
$\qquad\qquad\qquad\qquad$
Pregunta : Para un entero positivo de $n$, ¿cuántas maneras existen para la pila $$ n $1\times 2$ rectángulos ("$1$ fila y $2$ columnas" sólo bajo las siguientes condiciones?
Los rectángulos en la parte inferior están uno al lado del otro.
Un rectángulo no en la parte inferior y otro rectángulo a la derecha debajo de "superposición" sólo la mitad.
Deje que $f(n)$ ser el número de tales maneras. Entonces, curiosamente, hemos $$f(1)=1,\quad f(2)=3,\quad f(3)=9,\quad f(4)=27,\quad f(5)=81,\cdots$$
Tenemos $f(3)=9$ porque
$\qquad\qquad$
Por lo tanto, parece que podemos tener $f(n)=3^{n-1}$. Sin embargo, no he sido capaz de probar que.
He intentado utilizar la inducción. Sin embargo, no he sido capaz de encontrar una manera de utilizar la hipótesis de inducción. Ya que la respuesta parece muy simple, debe haber algo que me estoy perdiendo. Alguien puede ayudar?
