Demostrar que $a_n$ es un cuadrado perfecto si $n$ es incluso sin funciones de generación o desarrollo en serie de Taylor.

Question

Deje $a_n$ el número de enteros positivos cuyos dígitos son todos $1$, $3$, o $4$, y se suman a $n$.

Por ejemplo, $a_5 = 6$, ya que hay seis enteros con la propiedad deseada: $41, 14, 311, 131, 113$, e $11111$.

Demostrar que $a_n$ es un cuadrado perfecto si $n$ es incluso.

Hice algunos experimentos con el pequeño de los casos y se encontró la relación de recurrencia $a_n=a_{n-1}+a_{n-3}+a_{n-4}$. ¿Cómo debo continuar?

También, me gustaría una solución que no se utilice funciones de generación o de la serie de Taylor.

Answer 1

Es fácil observar numéricamente que $a_{2n} = F_n^2$ donde $F_n$ $n$ésimo número de Fibonacci. Que motiva buscando un bijection entre los enteros contado por $a_n$ y los pares ordenados de números de Fibonacci.

También es bien conocido que el $F_n$ cuenta las particiones de un $n\times 1$ rectángulo en $1\times1$ plazas y $2\times1$ rectángulos. Por ejemplo, $F_4=5$ porque:

Por lo $F_n^2$ cuenta las particiones de un $n\times2$ rectángulo en las mismas piezas. Por ejemplo, $F_3^2=9$ porque:

Para cada diagrama, dibujar una línea en zigzag a partir de la esquina superior izquierda, que va S a continuación, NE, a continuación, S, a continuación, NE ... hasta que termina en la parte inferior derecha:

Ahora romper el zig-zag en piezas tanto como sea posible, mientras que tener cada una de las $2\times1$ rectángulo es mentira todo en la misma pieza:

Finalmente, la lectura de las longitudes de las piezas en orden a lo largo de cada zig-zag resultados en los enteros contado por $a_n$:

$\displaystyle \begin{matrix} 111111&1113&1311\\1131&114&141\\3111&33&411 \end{matrix}$