Encontrar cada $n$ que $a_n$ es un número entero

Question

Vamos a definir $\{a_n\}$ $a_1=a_2=1$,$$a_{n+2}=a_{n+1}+\frac{a_n}{2}\ \ (n=1,2,\cdots).$$ Entonces, es la siguiente conjetura verdadera?

Una conjetura : Si $a_n$ es un número entero, entonces $n\le 8$.

Yo conjeturó esto mediante el uso de equipo, pero no tengo ninguna buena idea para probarlo. Alguien puede ayudar?

Answer 1

Vamos a escribir $a_n = \frac{p_n}{q_n}$, donde $\gcd(p_n,q_n)=1$. Luego tenemos a partir de la recurrencia de la relación que $$\frac{p_{n+2}}{q_{n+2}} = \frac{2q_n p_{n+1} + p_n q_{n+1}}{2q_nq_{n+1}}$$ con $p_1=q_1=p_2=q_2=1$. En particular, vemos que por cada $n$ se puede escribir $q_n = 2^{j_n}$ $j_n \ge 0$.

De la evidencia numérica suponemos las siguientes fórmulas de $j_n$:

• $j_{2k+1} = k$, donde $k \ge 0$
• $j_{2(2k+1)} = 2k$, donde $k \ge 0$
• $j_4 = 0$
• $j_{2^u(2k+1)} = 2^{u-1} (2k + 1) - u - 1$, donde $u \ge 2$, $k \ge 0$, $2^u(2k+1) \neq 4$

Note que $j_n = 0$ solo para $n=1,2,4,8$. Estos son los únicos valores para los cuales $a_n$ es un número entero.

Para demostrar todo esto, podemos definir la secuencia de $p_n$ por la relación de recurrencia $$p_n = 2^{j_n - j_{n-1}} p_{n-1} + 2^{j_n - j_{n-2} - 1} p_{n-2}, p_1 = p_2 = 1.$$ Tenemos que demostrar que $p_n$ es un número entero impar para todo $n \neq 4$ ($p_4 = 2$). Esto se puede hacer por inducción.

Aquí están los bocetos para la inducción pasos:

Case 1: $n-1$ es de la forma $2(2k+1)$

En este caso tenemos $p_n = 2 p_{n-1} + p_{n-2}$, se realiza por inducción.

Caso 1b: $n-1$ es de la forma $2^u(2k+1)$

En este caso tenemos $p_n = 2^{u+1} p_{n-1} + p_{n-2}$, se realiza por inducción.

El caso 2a: $n$ es de la forma $2(2k+1)$

En este caso tenemos $p_n = p_{n-1} + 2^u p_{n-2}$, se realiza por inducción.

Caso 2b: $n$ es de la forma $2^u(2k+1)$

En este caso tenemos $p_n = \frac{p_{n-1} + p_{n-2}}{2^u}$. Tenemos que demostrar que la potencia más grande de 2 $de$ que divide a $p_{n-1} + p_{n-2}$ es $2^de u$.

Para ello considerar la secuencia de $r_n = p_{4n-1} + p_{4n-2}$. Mediante el uso de la definición de la relación de $p_n$, uno puede demostrar que $r_n$ satisface la relación de recurrencia $r_n = 14 r_{n-1} - r_{n-2}$ con $r_1 = 4$, $r_2 = 56$. Una vez que hemos demostrado que $r_{2^u(2k+1)}$ es divisible por $2^{u+2}$, hemos terminado.

Podemos así considerar la secuencia de $s_n = r_n/4$, definidos por la misma recurrencia relación con los valores iniciales de $s_1 = 1$, $s_2 = 14$. Este es A007655 en OEIS. Tenemos la generación de la función $$S(x) = \frac{x}{1 - 14x + x^2}.$$ Para extraer los coeficientes de $x^{2^u(2k+1)}$, donde $u$ es fijo, se define la secuencia de funciones de generación $$S_n(x) = \frac{S_{n-1}(\sqrt{x}) + S_{n-1}(-\sqrt{x})}{2}, \quad S_1(x) = S(x).$$ Por inducción, vamos a ver que $$S_n(x) = \frac{A(1) \los puntos a(n-1) x}{1 - (n) x + x^2}$$ donde $A(1) = 14$, $A(n+1) = A(n)^2 - 2$. De hecho, $$\begin{eqnarray*} S_n(x) & = & \frac{\frac{A(1) \los puntos a(n-2) \sqrt{x}}{1 - (n-1) \sqrt{x} + x} - \frac{A(1) \los puntos a(n-2) \sqrt{x}}{1 + A(n-1) \sqrt{x} + x}}{2} \\ & = & \frac{Un(1) \los puntos a(n-2) (n-1) x}{(1 + x)^2 - (n-1)^2 x} \\ & = & \frac{Un(1) \los puntos a(n-1) x}{1 - (A(n-1)^2 - 2) x + x^2}. \end{eqnarray*}$$ Ahora $R_u(x) = \frac{S_{u+1}(\sqrt{x}) - S_{u+1}(-\sqrt{x})}{2\sqrt{x}}$ corresponde a la generación de la función de los términos de $r_{2^u(2k + 1)}$, donde $u$ es fijo. Tenemos $$\begin{eqnarray*} \frac{S_u(\sqrt{x}) - S_u(-\sqrt{x})}{2\sqrt{x}} & = & \frac{\frac{A(1) \dots(u-1) \sqrt{x}}{1 - (u-1) \sqrt{x} + x} + \frac{A(1) \dots(u-1) \sqrt{x}}{1 + (u-1) \sqrt{x} + x}}{2\sqrt{x}} \\ & = & \frac{Un(1) \dots(u-1) \sqrt{x}(1 + x)}{\sqrt{x}(1 - A(u) x + x^2)} \\ & = & \frac{Un(1) \dots(u-1) (1 + x)}{1 - (u) x + x^2}. \end{eqnarray*}$$ Claramente, por definición, cada uno $A(k)$ es divisible por $2$, pero no por $4$. Por lo tanto, el producto de $A(1) \dots(u-1) (u)$ frente $R(u)$ tiene exactamente $u$ factores de $2 dólares. Porque $A(u)$ es, incluso, los coeficientes de la serie de taylor de $\frac{1}{1 - (u) x + x^2}$ alternar entre pares e impares. Por lo tanto $\frac{1+x}{1 - (u) x + x^2}$ tiene impar de los coeficientes. Esto demuestra la reclamación.

Answer 2

Pensé que me gustaría escribir algunas observaciones que creo que son esencialmente una prueba, pero podría ser examinados y mejor presentado. Voy a tratar de volver y hacerlo yo mismo, pero yo sería feliz si alguien ve una buena manera de limpiar las cosas y lo hace en una de respuestas separada. (Si no, por favor, añadir comentarios a esta respuesta, así que puedo poner una edición aquí redirigir a los lectores.)

Comenzando con la OEIS secuencia de $1,2,3,8,11,30,41,112,\ldots$ en lhf la respuesta, que lhf señaló consiste en la alternancia de par e impar de términos, extracto de las condiciones para obtener la secuencia OEIS

$$0, 2, 8, 30, 112, 418, 1560, 5822, 21728, 81090, 302632, 1129438, 4215120, 15731042,\ldots$$

que satisface los dos términos de recursividad $a(n+1)=4a(n)-a(n-1)$. (Tenga en cuenta la adición de $0$ al principio. Este resulta ser bastante importante.) Si nos factor de us $2$, este nuevo alterna entre pares e impares:

$$0, 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, 564719, 2107560, 7865521,\ldots$$

así que dejando de lado la extraña términos da

$$0,4,56,780,10864,151316,2107560,\ldots$$

Ahora es fácil demostrar que en cualquier momento que elija cada término de una secuencia con dos términos de la recursividad, la nueva secuencia todavía satisface dos términos de recursividad: Si $a(n+1)=\alpha(n)+\beta(n-1)$, entonces $a(2n+2)=(\alpha^2+2\beta)a(2n)-\beta^2a(2n-2)$. Desde nuestro $\beta$ $-1$, esta nueva secuencia satisface la recursividad $a(n+1)=14a(n)-a(n-1)$, donde $14=4^2-2$. Esta vez podemos factor de us $4$ de la secuencia, dejando

$$0,1,14,195,2716,37829,526890,\ldots$$

que de nuevo suplentes par e impar de términos, por la simple razón de que $\alpha$ y $\beta$ para sus dos términos de recursividad también son pares e impares, así como $4$ y $-1$ eran en la secuencia de la que vino. Así que repetir:

$$0,14,2716,526890,\ldots$$

Factorizando los $14$ que hace que este

$$0,1,194,37635,\ldots$$

que satisface los dos términos de recursividad $a(n+1)=194a(n)-a(n-1)$, donde $194=14^2-2=(4^2-2)^2-2$. Está claro que lo que está ocurriendo: En el $m$th paso, terminamos con una secuencia de la forma

$$0,1,r_m,r_m^2-1,r_m^3-2r_m,\ldots$$

que satisface la recursividad $a(n+1)=r_ma(n)-a(n-1)$, con $r_m=r_{m-1}^2-2$. En particular, la secuencia de $r_m$'s $4,14,194,\ldots$, de modo que después de los primeros $4$, todos los términos son de $2$ veces un número impar. Así que cuando se pasa a la siguiente hornada de condiciones,

$$0,r_m,r_m^3-2r_m,\ldots$$

y, a continuación, el factor de la $r_m$ para obtener la siguiente secuencia de $0,1,r_{m+1},r_{m+1}^2-1,\ldots$, usted está tomando sólo una potencia de 2$$. Si usted piensa cuidadosamente acerca de qué significa todo esto, creo que explica los dientes de sierra en lhf del gráfico y muestra que usted termina con las grandes potencias de $2$ en el denominador de la OP original de la secuencia después de que el octavo término, como se conjeturó.

Answer 3

Respuesta parcial. Trabajo en progreso.

Deje de $b_n= 2^{\lfloor n/2 \rfloor} a_n$. Esta secuencia es bien conocido: oeis.org/A048788: $$ 1, 2, 3, 8, 11, 30, 41, 112, 153, 418, 571, 1560, 2131, 5822, \puntos $$

Satisface $$ b_{2n} = 2b_{2n-1} + b_{2n-2} $$ $$ b_{2n+1} = b_{2n} + b_{2n-1} $$

Es claro a partir de estas ecuaciones y las condiciones iniciales que $b_n \bmod 2$ es $1,0,1,0,1,\dots$. En particular, $b_n$ es impar por $$ n impar. Esto implica que $a_n$ no es un entero $n$ impar.

Mi estrategia original, que conducen a la solución anterior, es considerar el número de lugares decimales que se requiere para representar a $a_n$. Empíricamente, de la siguiente manera $n/2$, como el argumento anterior muestra, pero para algunos $n$. en particular, los poderes de $2$, el número de lugares decimales que se desciende notablemente. Ver la foto de abajo. El enfoque de arriba muestra que $n/2$ suficiente, pero necesito un menor obligado, no un límite superior.