I am going through official solutions for IMO'09 problems. Currently stuck at solution 2 for N7. I am copying parts that confuse me below, but if anyone is interested in the rest, this is a link to full pdf.
Now, here are my questions:
- Letting $s_n=(ab)^n-\gamma_1\left(\frac{a}{b}\right)^n-\ldots-\gamma_k\left(\frac{a}{b^{2k-1}}\right)^n$, I don not quite get how they derive $z_n=s_n+O\left(\frac{b}{a}\right)^n$. Will the following explanation be good enough?
If we let $\alpha_n=z_n-s_n$, then $(s_n+\alpha_n)^2=z_n^2\equiv z_n^2+0$. From the solution $z_n^2+O(B^n)=\{s_n+O\left(\frac{b}{a}\right)^n\}^2$, and since $0=O(B^n)$, we necessarily have $\alpha_n=O\left(\frac{b}{a}\right)^n$. Is that it?
When coefficients $\delta_i$ are introduced, $\delta_0$ is determined to be greater than $0$ because $z_n>0$. How? Is it because for large values of $n$ term $(ab)^n$ will dominate, so its coefficient needs to be positive?
After the last centered formula they derive $a=b^{k-1}$ from asymptotic calculations. What are these calculations and why does $a=b^{k-1}$ follow from them? Something like the following?
If we assign $\epsilon_n$ to be $O\left(\frac{A}{B^k}\right)^n$, then $\epsilon_n\to0$, because $A<B^k$. If in the last centered formula we now move everything, except $\epsilon_n$, to the left side, we will have, in particular, $A^nB^n(1-\delta_0^2)$ there. If $1-\delta_0^2\neq0$ this term is dominating for large $n$ and thus the left side will never tend to $0$, but the right side tends to $0$, so $1-\delta_0^2=0$. And so on for $\delta_1$ and the rest of them…
Is that it?
- Immediately after what is discussed in 3. they infer that there should be some $P\in\mathbb{Q}[x]$ for which $(X-1)(X^{k-1}-1)=P(X)^2$. Why? As far as I can see, if we let $X=B^n$, then $A^n=X^{k-1}$ and we have $(A^n-1)(B^n-1)=(X-1)(X^{k-1}-1)$. If we now view it as polynomial in variable $X$, from the assumption that $(A^n-1)(B^n-1)$ is a perfect square for all $n$ this polynomial maps countably infinite number of integers to perfect squares. How do we now derive that it necessarily needs to be a perfect square of some polynomial in $X$?
Thank you.
$\def\peq{\mathrel{\phantom{=}}{}}$First, there is a typo in the definition of $\{γ_n\}$. It should be$$ 2γ_1 = 1, \quad γ_n = \sum_{j = 1}^{n - 1} γ_j γ_{n - j}. \quad (n \geqslant 2) $$ For the first question, there is some abuse of notations in the official answer. In fact, since $0 < γ_n < 1$ for all $n \geqslant 1$ and $B^{k - 1} \leqslant A < B^k$, then\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*} Note that $z_n \sim (ab)^n\ (n → ∞)$ and $a > b$, then (1) implies $s_n \sim (ab)^n\ (n → ∞)$ and$$ |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 → ∞ $$ which implies $z_n = s_n + O\left( \left( \dfrac{b}{a} \right)^n \right)$.
For the second question, your reasoning is correct.
For the third question, it can be derived analogously to (1) that for some $N_0 \geqslant 1$ and any $n \geqslant N_0$,\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*} Note that $A > B$. First, dividing by $(AB)^n$ on both sides of (2) and making $n → ∞$ yields $δ_0^2 = 1$, thus $δ_0 = 1$. Next, subtracting $(AB)^n$ from both sides of (2), then dividing by $A^n$ and making $n → ∞$ yields $2δ_0 δ_1 = 1$, thus $δ_1 = \dfrac{1}{2}$. Now, for $m = 2, \cdots, k - 2$, each time subtracting$$(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 $$ from both sides of (2), then dividing by $\left( \dfrac{A}{B^{m - 1}} \right)^n$ and making $n → ∞$ yields $2δ_m = \sum\limits_{j = 1}^{m - 1} δ_j δ_{m - j}$. Now, (2) reduces to\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*} Suppose $a > b^{k - 1}$, then $A > B^{k - 1}$ and analogously $2δ_{k - 1} = \sum\limits_{j = 1}^{k - 2} δ_j δ_{k - 1 - j}$. Then (3) becomes$$ -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), $$ and divinding by $B^n$ and making $n → ∞$ leads to contradiction (Note that $A < B^k$). Thus, $a = b^{k - 1}$ and $k \geqslant 3$.
For the last question, I do not understand the logic within that step, but here is a way using similar ideas: Since $a = b^{k - 1}$, then$$ (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. $$ Thus,$$ (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, $$ which leads to contradiction since $k \geqslant 3$ and $\dfrac{X^{2(k - 1)} - 1}{X^2 - 1}$ has no multiple zeros.