Si una secuencia de números naturales satisface $\gcd(a_{i+1},a_{i})>a_{i-1}$, entonces el $a_{n}>2^n$

Question

Dada una secuencia de $\{a_{n}\}$ $\mathbb{N}$ tal que $\gcd(a_{i+1},a_{i})>a_{i-1},$ para cualquier $i\ge 2$, muestran que el $a_{n}>2^{n-1}$.

Gracias a todos, mi amigo me preguntó acerca de este problema y creo que este problema es realmente interesante.

Answer 1

(Nota, que $\mathbb N$ no se incluyen los $0$ en mi respuesta)

Esto parece muy interesante problema. Como @MarcvanLeeuwen señaló en su comentario, el problema como usted lo dijo, no es cierto. De hecho, se puede demostrar, que el contraejemplo dio es la peor posible:

Teorema: Vamos a $(a_n)_{n\in\mathbb N}$ ser una secuencia en $\mathbb N$, de tal manera que $a_i<(a_{i+1},a_{i+2})$ todos los $i\in\mathbb N$, $a_i\geq 2^{i-1}$ todos los $i\in\mathbb N$.

Prueba: en Primer lugar, tenga en cuenta, que $(a_n)$ es estrictamente creciente, ya que: $$a_i<(a_{i+1},a_{i+2})\leq a_{i+1}$$ Además, vamos a utilizar repetidamente el hecho de $$ (*1):\qquad \forall a,b\in\mathbb Z: (a,b)\leq |a-b|$$ (esto es cierto como $(a,b)|a,b$ implica $(a,b)|a-b$).

Tenemos que probar que el teorema es verdadero, por $i=1,2,3$:

• $a_1\in\mathbb N$ implica $a_1\geq 1$.
• $a_2>a_1\geq 1$ implica $a_1\geq 2$.
• $a_3>a_2\geq 2$, lo $a_3\geq 3$. Si $a_3=3$, $a_2=2$ $a_1=1$ $1=a_1<(a_2,a_3)=(2,3)=1$ es falso. Por lo $a_3\geq 4$.

Para $i+1>3$, podemos demostrar el teorema por inducción, por lo que asumimos que es cierto, por $i, i-1$$i-2$.

Hay $k,l\in\mathbb N$, de tal manera que $$(a_i,a_{i+1})\cdot k=a_{i+1} \qquad (a_i,a_{i+1})\cdot l=a_i$$

• $k\leq 2$: Uso ($*1$): $$a_{i+1}=k\cdot (a_i, a_{i+1})\leq k\cdot ( a_{i+1} - a_i ) \leq 2 \cdot ( a_{i+1} - a_i )$$ Por lo $a_{i+1}\geq 2a_i=2\cdot 2^{i-1}=2^i$ por la hipótesis de inducción.
• $k\geq 4$: Esto se sigue inmediatamente aplicando la hipótesis de inducción. $$a_{i+1} = k \cdot (a_i,a_{i+1}) \geq 4 \cdot (a_i,a_{i+1}) > 4a_{i-1} = 4\cdot 2^{i-2} = 2^i$$
• $k=3$ $l=1$ . A continuación,$a_{i+1}=3a_i\geq 3\cdot 2^{i-1} \geq 2^i$.

Como $a_i<a_{i+1}$ implica $l<k$, el único caso es el siguiente:

• $k=3$ $l=2$ . Denotar $m:=(a_i,a_{i+1})$, lo $a_i=2m$$a_{i+1}=3m$.
  • $m\geq \frac{8}{3}a_{i-2}:$ $$a_{i+1}=3m\geq 3\cdot \frac{8}{3}a_{i-2}=8a_{i-2}\geq 8\cdot 2^{i-3}=2^i$$
  • $m\geq \frac{4}{3}a_{i-1}:$ Igual que antes: $$a_{i+1}=3m\geq 3\cdot \frac{4}{3}a_{i-1}=4a_{i-1}\geq 4\cdot 2^{i-2}=2^i$$
  • $m<\frac{8}{3}a_{i-2}$ ($*2$) y $m<\frac{4}{3}a_{i-1}$ ($*3$): Entonces $$a_{i-1}<(a_i,a_{i+1})=(2m,3m)=m$$ El uso de este y de ($*1)$, obtenemos: $$a_{i-2}<(a_{i-1},a_i)=(a_{i-1},a_i-a_{i-1})\leq |a_i-2a_{i-1}|=|2m-2a_{i-1}|=2(m-a_{i-1})$$ Reagrupar esta ecuación para obtener: $$(*4):\quad m > a_{i-1} + \frac{1}{2} a_{i-2}$$ Entonces: $$m\overset{(*4)}{>} a_{i-1} + \frac{1}{2} a_{i-2}\overset{(*3)}{>} \frac{3}{4}m+\frac{1}{2} a_{i-2} \Rightarrow \frac{1}{4}m>\frac{1}{2}a_{i-2} \Rightarrow m > 2a_{i-2}$$ El uso de este y de ($*4$) de nuevo: $$\frac{3}{2}a_{i-2} < \frac{3}{4}m \overset{(*3)}{<} a_{i-1} \overset{(*4)}{<} m - \frac{1}{2} a_{i-2} \overset{(*2)}{<} \frac{8}{3}a_{i-2} - \frac{1}{2}a_{i-2} = \frac{13}{16}a_{i-2} < \frac{3}{2} a_{i-2}$$ Esto es una contradicción, por lo que este caso no es posible.

---

EDIT: he editado el post para dar la anterior prueba de la estrecha obligado. Yo no eliminar previamente probado más débiles límites, ya que son pruebas simples y alguien podría encontrar interesantes.

Más débil de los límites, es decir, las pruebas para el $a_i\geq b^{i-1}$ algunos $b<2$:

Lema: Vamos a $(a_n)_{n\in\mathbb N}$ ser una secuencia en $\mathbb N$, de tal manera que $a_i<(a_{i+1},a_{i+2})$ todos los $i\in\mathbb N$, $a_{i+2}>a_{i+1}+a_i$ todos los $i\in\mathbb N$.

Prueba: La sucesión es estrictamente creciente desde $a_i<(a_{i+1},a_{i+2})\leq a_{i+1}$. $(a_{i+1},a_{i+2})$ divide tanto a a$a_{i+1}$$a_{i+2}$, por lo tanto, también su diferencia $a_{i+2}-a_{i+1}$. Puesto que ambos son positivos, esto implica $(a_{i+1},a_{i+2})\leq a_{i+2}-a_{i+1}$ en los rendimientos. $$a_{i+2}=(a_{i+2}-a_{i+1})+a_{i+1}\geq (a_{i+2},a_{i+1}) + a_{i+1} > a_i + a_{i+1}$$

Teorema: Vamos a $(a_n)_{n\in\mathbb N}$ ser una secuencia en $\mathbb N$, de tal manera que $a_i<(a_{i+1},a_{i+2})$ todos los $i\in\mathbb N$, $a_i\geq F_i$ todos los $i\in\mathbb N$. (donde $F_i$ indica el $i$-ésimo número de Fibonacci)

Prueba: Esto es cierto para $i=1,2$. Para $i>2$ a la conclusión de que la inducción por: $$F_{n+2}=F_n+F_{n+1}\leq a_n+a_{n+1}<a_{n+2}$$

Como $F_n\approx \frac{\varphi^n}{\sqrt{5}}$ donde $\varphi\approx 1.61$ es la proporción áurea, se concluyó que para algunas de algunas límite inferior en el espíritu por encima de con $b$, ligeramente por debajo de $\varphi$. Más débil, pero más sencillo es $b=\sqrt{2}$:

Teorema: Vamos a $(a_n)_{n\in\mathbb N}$ ser una secuencia en $\mathbb N$, de tal manera que $a_i<(a_{i+1},a_{i+2})$ todos los $i\in\mathbb N$, $a_i\geq (\sqrt{2})^{i-1}$ todos los $i\in\mathbb N$.

Prueba: Como $a_n$ es estrictamente creciente, tenemos $a_1\geq 1$$a_2\geq 2$, así que esto es cierto para $i=1,2$. Para $i>2$ inducción: $$a_{n+2} > a_{n+1}+a_n > a_n + a_n = 2a_n \geq 2\cdot (\sqrt{2})^{i-1}= (\sqrt{2})^{i+1}$$

Answer 2

Suponiendo que menor demanda por pedir sólo para demostrar $a_n\geq2^n$, y añadir la hipótesis de que la $a_1\geq2$, de modo que, al menos, la desigualdad se mantenga por $n=1$, entonces uno obtiene un contraejemplo de tomar $(a_1,a_2,a_3,\ldots)=(2,3,6,12,\ldots)$, desde $3<2^2$, $6<2^3$ y así sucesivamente. Si ustedes insisten $a_0$ se define, establece a$~1$ (independientemente de la cuestión de si $a_0$ está definido o no, no requieren $\gcd(a_2,a_1)>a_0$).

En breve tendrá a estado bastante no evidentes requisitos adicionales para obtener una declaración de que uno podría incluso comenzar a esperanza para ser verdad.