Un par de grandes preguntas sobre un problema de teoría de números

Question

Un par de grandes preguntas sobre un problema de teoría de números

asintóticos
Matemáticas
concurso-matematicas
teoría de los números

usuario75619

Estoy revisando las soluciones oficiales para los problemas de IMO'09. Actualmente atascado en la solución 2 para N7. Estoy copiando partes que me confunden a continuación, pero si alguien está interesado en el resto, este es un enlace al pdf completo.

Ahora, aquí están mis preguntas:

Alquiler $s_n=(ab)^n-\gamma_1\left(\frac{a}{b}\right)^n-\ldots-\gamma_k\left(\frac{a}{b^{2k-1}}\right)^n$ , no entiendo muy bien cómo se derivan $z_n=s_n+O\left(\frac{b}{a}\right)^n$ . ¿Será lo suficientemente buena la siguiente explicación?

si dejamos $\alpha_n=z_n-s_n$ , entonces $(s_n+\alpha_n)^2=z_n^2\equiv z_n^2+0$ . de la solucion $z_n^2+O(B^n)=\{s_n+O\left(\frac{b}{a}\right)^n\}^2$ , y desde $0=O(B^n)$ , necesariamente tenemos $\alpha_n=O\left(\frac{b}{a}\right)^n$ . ¿Es asi?

Cuando los coeficientes $\delta_i$ son introducidos, $\delta_0$ se determina que es mayor que $0$ porque $z_n>0$ . ¿Cómo? ¿Es porque para valores grandes de $n$ término $(ab)^n$ dominará, por lo que su coeficiente debe ser positivo?
Después de la última fórmula centrada se derivan $a=b^{k-1}$ de cálculos asintóticos. ¿Cuáles son estos cálculos y por qué $a=b^{k-1}$ seguir de ellos? ¿Algo como lo siguiente?

si asignamos $\epsilon_n$ ser $O\left(\frac{A}{B^k}\right)^n$ , entonces $\epsilon_n\to0$ , porque $A<B^k$ . Si en la última fórmula centrada ahora movemos todo, excepto $\epsilon_n$ , al lado izquierdo, tendremos, en particular, $A^nB^n(1-\delta_0^2)$ allá. Si $1-\delta_0^2\neq0$ este término es dominante para grandes $n$ y así el lado izquierdo nunca tenderá a $0$ , pero el lado derecho tiende a $0$ , entonces $1-\delta_0^2=0$ . Y así sucesivamente para $\delta_1$ y el resto de ellos...

¿Es asi?

Inmediatamente después de lo discutido en 3. infieren que debería haber algún $P\in\mathbb{Q}[x]$ para cual $(X-1)(X^{k-1}-1)=P(X)^2$ . ¿Por qué? Por lo que puedo ver, si dejamos $X=B^n$ , entonces $A^n=X^{k-1}$ y tenemos $(A^n-1)(B^n-1)=(X-1)(X^{k-1}-1)$ . Si ahora lo vemos como polinomio en variable $X$ , del supuesto de que $(A^n-1)(B^n-1)$ es un cuadrado perfecto para todos $n$ este polinomio asigna un número infinito numerable de enteros a cuadrados perfectos. ¿Cómo deducimos ahora que necesariamente tiene que ser un cuadrado perfecto de algún polinomio en $X$ ?

Gracias.

Respuestas (1)

Un par de grandes preguntas sobre un problema de teoría de números

Ѕᴀᴀᴅ · Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$ En primer lugar, hay un error tipográfico en la definición de $\{γ_n\}$ . Debería ser

2 γ_{1} = 1, γ_{norte} = \sum_{j = 1}^{norte - 1} γ_{j} γ_{norte - j} . (norte ⩾ 2)

$2γ_1 = 1, \quad γ_n = \sum_{j = 1}^{n - 1} γ_j γ_{n - j}. \quad (n \geqslant 2)$ Para la primera pregunta, hay cierto abuso de notaciones en la respuesta oficial. De hecho, desde

0 < γ_{n} < 1

$0 < γ_n < 1$ para todos

n ⩾ 1

$n \geqslant 1$ y

B^{k - 1} ⩽ A < B^{k}

$B^{k - 1} \leqslant A < B^k$ , entonces

\begin{aligned} s_{norte}^{2} & = {((a b)^{norte} - \sum_{j = 1}^{k} γ_{j} {(\frac{a}{b^{2 j - 1}})}^{norte})}^{2} \\ = ((a b)^{norte})^{2} - 2 (a b)^{norte} \cdot \sum_{j = 1}^{k} γ_{j} {(\frac{a}{b^{2 j - 1}})}^{norte} + {(\sum_{j = 1}^{k} γ_{j} {(\frac{a}{b^{2 k - 1}})}^{norte})}^{2} \\ = (A B)^{norte} - \sum_{j = 1}^{k} 2 γ_{j} {(\frac{A}{B^{j - 1}})}^{norte} + \sum_{j = 2}^{k} \sum_{yo = 1}^{j - 1} γ_{yo} γ_{j - yo} {(\frac{a}{b^{2 yo - 1}})}^{norte} {(\frac{a}{b^{2 (j - yo) - 1}})}^{norte} \\ + \sum_{\begin{matrix} 1 ⩽ j, yo ⩽ k \\ j + yo ⩾ k + 1 \end{matrix}} γ_{j} γ_{yo} {(\frac{a}{b^{2 j - 1}})}^{norte} {(\frac{a}{b^{2 yo - 1}})}^{norte} \\ = (A B)^{norte} - \sum_{j = 1}^{k} 2 γ_{j} {(\frac{A}{B^{j - 1}})}^{norte} + \sum_{j = 2}^{k} \sum_{yo = 1}^{j - 1} γ_{yo} γ_{j - yo} {(\frac{A}{B^{j - 1}})}^{norte} + O ({(\frac{A}{B^{k}})}^{norte}) \\ = (A B)^{norte} - 2 γ_{1} A^{norte} - \sum_{j = 2}^{k} (2 γ_{j} - \sum_{yo = 1}^{j - 1} γ_{yo} γ_{j - yo}) {(\frac{A}{B^{j - 1}})}^{norte} + O ({(\frac{A}{B^{k}})}^{norte}) \\ (1) & = (A B)^{norte} - A^{norte} + O ({(\frac{A}{B^{k}})}^{norte}) = z_{norte}^{2} + B^{norte} - 1 + O (B^{norte}) . \end{aligned}

$\begin{align*} s_n^2 &= \left( (ab)^n - \sum_{j = 1}^k γ_j \left( \frac{a}{b^{2j - 1}} \right)^n \right)^2\\ &= ((ab)^n)^2 - 2(ab)^n · \sum_{j = 1}^k γ_j \left( \frac{a}{b^{2j - 1}} \right)^n + \left( \sum_{j = 1}^k γ_j \left( \frac{a}{b^{2k - 1}} \right)^n \right)^2\\ &= (AB)^n - \sum_{j = 1}^k 2γ_j \left( \frac{A}{B^{j - 1}} \right)^n + \sum_{j = 2}^k \sum_{l = 1}^{j - 1} γ_l γ_{j - l} \left( \frac{a}{b^{2l - 1}} \right)^n \left( \frac{a}{b^{2(j - l) - 1}} \right)^n\\ &\peq + \sum_{\substack{1 \leqslant j, l \leqslant k\\j + l \geqslant k + 1}} γ_j γ_l \left( \frac{a}{b^{2j - 1}} \right)^n \left( \frac{a}{b^{2l - 1}} \right)^n\\ &= (AB)^n - \sum_{j = 1}^k 2γ_j \left( \frac{A}{B^{j - 1}} \right)^n + \sum_{j = 2}^k \sum_{l = 1}^{j - 1} γ_l γ_{j - l} \left( \frac{A}{B^{j - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right)\\ &= (AB)^n - 2γ_1 A^n - \sum_{j = 2}^k \left( 2γ_j - \sum_{l = 1}^{j - 1} γ_l γ_{j - l} \right) \left( \frac{A}{B^{j - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right)\\ &= (AB)^n - A^n + O\left( \left( \frac{A}{B^k} \right)^n \right) = z_n^2 + B^n - 1 + O(B^n). \tag{1} \end{align*}$ Tenga en cuenta que

z_{n} \sim (a b)^{n} (n \to \infty)

$z_n \sim (ab)^n\ (n → ∞)$ y

a > b

$a > b$ , entonces (1) implica

s_{n} \sim (a b)^{n} (n \to \infty)

$s_n \sim (ab)^n\ (n → ∞)$ y

| z_{norte} - s_{norte} | = \frac{| z_{norte}^{2} - s_{norte}^{2} |}{z_{norte} + s_{norte}} \sim \frac{B^{norte}}{2 (a b)^{norte}} = 2 {(\frac{b}{a})}^{norte}, norte \to \infty

$|z_n - s_n| = \frac{|z_n^2 - s_n^2|}{z_n + s_n} \sim \frac{B^n}{2(ab)^n} = 2\left( \frac{b}{a} \right)^n, \quad n → ∞$ lo que implica

z_{n} = s_{n} + O ({(\frac{b}{a})}^{n})

$z_n = s_n + O\left( \left( \dfrac{b}{a} \right)^n \right)$ .

Para la segunda pregunta, su razonamiento es correcto.

Para la tercera pregunta, se puede derivar análogamente a (1) que para algunos $N_0 \geqslant 1$ y cualquiera $n \geqslant N_0$ ,

\begin{aligned} A^{norte} B^{norte} - A^{norte} - B^{norte} + 1 = z_{norte}^{2} = {(d_{0} (a b)^{norte} - \sum_{j = 1}^{k} d_{j} {(\frac{a}{b^{2 j - 1}})}^{norte})}^{2} \\ (2) & = d_{0}^{2} (A B)^{norte} - 2 d_{0} d_{1} A^{norte} - \sum_{j = 2}^{k} (2 d_{0} d_{j} - \sum_{yo = 1}^{j - 1} d_{yo} d_{j - yo}) {(\frac{A}{B^{j - 1}})}^{norte} + O ({(\frac{A}{B^{k}})}^{norte}) . \end{aligned}

$\begin{align*} &\peq A^n B^n - A^n - B^n + 1 = z_n^2 = \left( δ_0 (ab)^n - \sum_{j = 1}^k δ_j \left( \frac{a}{b^{2j - 1}} \right)^n \right)^2\\ &= δ_0^2 (AB)^n - 2δ_0 δ_1 A^n - \sum_{j = 2}^k \left( 2δ_0 δ_j - \sum_{l = 1}^{j - 1} δ_l δ_{j - l} \right) \left( \frac{A}{B^{j - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right). \tag{2} \end{align*}$ Tenga en cuenta que

A > B

$A > B$ . Primero, dividiendo por

(A B)^{n}

$(AB)^n$ a ambos lados de (2) y haciendo

n \to \infty

$n → ∞$ rendimientos

δ_{0}^{2} = 1

$δ_0^2 = 1$ , de este modo

δ_{0} = 1

$δ_0 = 1$ . A continuación, restando

(A B)^{n}

$(AB)^n$ de ambos lados de (2), luego dividiendo por

A^{n}

$A^n$ y haciendo

n \to \infty

$n → ∞$ rendimientos

2 δ_{0} δ_{1} = 1

$2δ_0 δ_1 = 1$ , de este modo

δ_{1} = \frac{1}{2}

$δ_1 = \dfrac{1}{2}$ . Ahora para

m = 2, \dots, k - 2

$m = 2, \cdots, k - 2$ , cada vez restando

(A B)^{norte} - A^{norte} - \sum_{j = 2}^{metro - 1} (2 d_{j} - \sum_{yo = 1}^{j - 1} d_{yo} d_{j - yo}) {(\frac{A}{B^{j - 1}})}^{norte}

$(AB)^n - A^n - \sum_{j = 2}^{m - 1} \left( 2δ_j - \sum_{l = 1}^{j - 1} δ_l δ_{j - l} \right) \left( \frac{A}{B^{j - 1}} \right)^n$ de ambos lados de (2), luego dividiendo por

{(\frac{A}{B^{m - 1}})}^{n}

$\left( \dfrac{A}{B^{m - 1}} \right)^n$ y haciendo

n \to \infty

$n → ∞$ rendimientos

2 δ_{m} = \sum_{j = 1}^{m - 1} δ_{j} δ_{m - j}

$2δ_m = \sum\limits_{j = 1}^{m - 1} δ_j δ_{m - j}$ . Ahora, (2) se reduce a

\begin{aligned} - B^{norte} + 1 & = - (2 d_{0} d_{k - 1} - \sum_{yo = 1}^{k - 2} d_{yo} d_{k - 1 - yo}) {(\frac{A}{B^{k - 2}})}^{norte} \\ (3) & - (2 d_{0} d_{k} - \sum_{yo = 1}^{k - 1} d_{yo} d_{k - yo}) {(\frac{A}{B^{k - 1}})}^{norte} + O ({(\frac{A}{B^{k}})}^{norte}) . \end{aligned}

$\begin{align*} -B^n + 1 &= - \left( 2δ_0 δ_{k - 1} - \sum_{l = 1}^{k - 2} δ_l δ_{k - 1 - l} \right) \left( \frac{A}{B^{k - 2}} \right)^n\\ &\peq - \left( 2δ_0 δ_k - \sum_{l = 1}^{k - 1} δ_l δ_{k - l} \right) \left( \frac{A}{B^{k - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right). \tag*{(3)} \end{align*}$ Suponer

a > b^{k - 1}

$a > b^{k - 1}$ , entonces

A > B^{k - 1}

$A > B^{k - 1}$ y análogamente

2 δ_{k - 1} = \sum_{j = 1}^{k - 2} δ_{j} δ_{k - 1 - j}

$2δ_{k - 1} = \sum\limits_{j = 1}^{k - 2} δ_j δ_{k - 1 - j}$ . Entonces (3) se convierte en

- B^{norte} + 1 = - (2 d_{0} d_{k} - \sum_{yo = 1}^{k - 1} d_{yo} d_{k - yo}) {(\frac{A}{B^{k - 1}})}^{norte} + O ({(\frac{A}{B^{k}})}^{norte}),

$-B^n + 1 = -\left( 2δ_0 δ_k - \sum_{l = 1}^{k - 1} δ_l δ_{k - l} \right) \left( \frac{A}{B^{k - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right),$ y dividiendo por

B^{n}

$B^n$ y haciendo

n \to \infty

$n → ∞$ conduce a la contradicción (Tenga en cuenta que

A < B^{k}

$A < B^k$ ). De este modo,

a = b^{k - 1}

$a = b^{k - 1}$ y

k ⩾ 3

$k \geqslant 3$ .

Para la última pregunta, no entiendo la lógica dentro de ese paso, pero aquí hay una forma de usar ideas similares: Dado que $a = b^{k - 1}$ , entonces

(b^{2 norte (k - 1)} - 1) (b^{2 norte} - 1) = z_{norte}^{2} = {(d_{0} b^{norte k} - \sum_{j = 1}^{k} d_{j} b^{norte (k - 2 j)})}^{2} ⟹ ((b^{norte})^{2 (k - 1)} - 1) ((b^{norte})^{2} - 1) (b^{norte})^{2 k} = {(d_{0} (b^{norte})^{2 k} - \sum_{j = 1}^{k} d_{j} (b^{norte})^{2 (k - j)})}^{2} .

$(b^{2n(k - 1)} - 1)(b^{2n} - 1) = z_n^2 = \left( δ_0 b^{nk} - \sum_{j = 1}^k δ_j b^{n(k - 2j)} \right)^2\\ \Longrightarrow ((b^n)^{2(k - 1)} - 1)((b^n)^2 - 1)(b^n)^{2k} = \left( δ_0 (b^n)^{2k} - \sum_{j = 1}^k δ_j (b^n)^{2(k - j)} \right)^2.$ De este modo,

(X^{2 (k - 1)} - 1) (X^{2} - 1) X^{2 k} = {(d_{0} X^{2 k} - \sum_{j = 1}^{k} d_{j} X^{2 (k - j)})}^{2} = (q (X))^{2},

$(X^{2(k - 1)} - 1)(X^2 - 1)X^{2k} = \left( δ_0 X^{2k} - \sum_{j = 1}^k δ_j X^{2(k - j)} \right)^2 = (Q(X))^2,$ lo que lleva a una contradicción ya que

k ⩾ 3

$k \geqslant 3$ y

\frac{X^{2 (k - 1)} - 1}{X^{2} - 1}

$\dfrac{X^{2(k - 1)} - 1}{X^2 - 1}$ no tiene múltiples ceros.

Cuando dices que abusan de la notación, ¿quieres decir que deberíamos preferir tener O grande solo en un lado de la ecuación?
@ user75619 En realidad me refiero al escribir ${((a b)^{norte} - \sum_{j = 1}^{k} γ_{k} {(\frac{a}{b^{2 j - 1}})}^{norte} + O ({(\frac{b}{a})}^{norte}))}^{2} = A^{norte} B^{norte} - 2 γ_{1} A^{norte} - \sum_{j = 2}^{k} (2 γ_{j} - \sum_{yo = 1}^{j - 1} γ_{yo} γ_{j - yo}) {(\frac{A}{B^{j - 1}})}^{norte} + O ({(\frac{A}{B^{k}})}^{norte}) + O (B^{norte}),$ $\left((ab)^n-\sum_{j=1}^kγ_k\left(\frac a{b^{2j-1}}\right)^n+O\left(\left(\frac ba\right)^n\right)\right)^2\\=A^nB^n-2γ_1A^n-\sum_{j=2}^k\left(2γ_j-\sum_{l=1}^{j-1}γ_lγ_{j-l}\right)\left(\frac A{B^{j-1}}\right)^n+O\left(\left(\frac A{B^k}\right)^n\right)+O(B^n),$ es muy difícil decir lo que sale de $O\left(\left(\dfrac ba\right)^n\right)$ y lo que entra $O\left(\left(\dfrac A{B^k}\right)^n\right)$ y $O(B^n)$ .
Recibí tu explicación en 1., todavía me pregunto si tenía razón al hacer lo que hice. Si elimináramos el abuso de la notación y reescribiéramos su afirmación de esta manera $si (s_{norte} + α_{norte})^{2} = z_{norte}^{2} + β_{norte}, entonces$ $\text{ if }(s_n+\alpha_n)^2=z_n^2+\beta_n, \text{ then }$ $α_{norte} = O {(\frac{b}{a})}^{norte} \Rightarrow β_{norte} = O (B^{norte}) y$ $\alpha_n=O\left(\frac{b}{a}\right)^n\Rightarrow\beta_n=O(B^n) \text { and }$ $β_{norte} = O (B^{norte}) \Rightarrow α_{norte} = O {(\frac{b}{a})}^{norte}$ $\beta_n=O(B^n)\Rightarrow\alpha_n=O\left(\frac{b}{a}\right)^n$ ¿podríamos deducir entonces que $\alpha_n=z_n-s_n$ es necesariamente $O\left(\frac{b}{a}\right)^n$ , desde $z_n^2+0=(s_n+\alpha_n)^2$ y $0=O(B^n)$ ?
@ user75619 La implicación en las nuevas afirmaciones en los comentarios no parece necesariamente cierta.
Entonces supongo que no entiendo completamente cómo funciona Big O, lol... Mi impresión fue que $(s_n+O\left(\frac{b}{a}\right)^n)^2=z_n^2+O(B^n)$ se puede leer en ambas direcciones, y cuando se lee de derecha a izquierda significa que si estuviéramos sumando algunos números $\beta_n$ a $z_n^2$ entonces habría algunos números $\alpha_n$ tal que $(s_n+\alpha_n)^2=z_n^2+\beta_n$ y $\alpha_n$ sería $O\left(\frac{b}{a}\right)^n$ , siempre y cuando $\beta_n$ eran $O(B^n)$ .
Eso lo sé... Pero tenía la impresión de que desde $0\leq M_2|B^n|$ debería implicar que tenía que haber alguna constante $M_1>0$ tal que $|\alpha_n|\leq M_1\left|(b/a)^n\right|$ y $(s_n+\alpha_n)^2=z_n^2$ .
@ user75619 Como dije, esta implicación no es necesariamente cierta. Al menos necesita más pruebas.

Un par de grandes preguntas sobre un problema de teoría de números

usuario75619

Respuestas (1)

Ѕᴀᴀᴅ

usuario75619

Ѕᴀᴀᴅ

usuario75619

Ѕᴀᴀᴅ

usuario75619

usuario75619

Ѕᴀᴀᴅ

usuario75619

Número de dígitos en 8n8n8^n en base 666

Existencia de un subconjunto tal que el producto de sus elementos es un cuadrado perfecto

Demostrar que no existen PRIMOS EXTREMOS de 5 dígitos.

Número de composiciones de nnn tales que cada término es menor que igual a kkk

Pregunta modelo PRMO: "El mcm menor de 20 números naturales, no necesariamente diferentes, cuya suma es 413, es _________"

Demostrar que existe un entero par al final

Mostrando que a2+b2+c2+d2+e2+65=abcdea2+b2+c2+d2+e2+65=abcdea^2+b^2+c^2+d^2+e^2+65=abcde tiene soluciones enteras mayores que 201820182018?

La distancia entre la potencia de 3 y la mayor potencia de 2

Área del trapezoide dados todos los lados: ¿Por qué es esto un problema de Olimpiada? [cerrado]

¿Aplicaciones de la Integral Exponencial?