Continuing the number theoretic sequence trajectory.
Let \(f\), \(g \in \mathbf{Z}[X]\) be two nonconstant polynomials such that \(f(n) \mid g(n)\) for infinitely many \(n\). Prove that \(f\) divides \(g\) in \(\mathbf{Q}[X]\).
Since \(f(n) \mid g(n)\) for infinitely many \(n\), \(\deg f < \deg g\). Divide \(g\) by \(f\) in \(\mathbf{Q}[X]\) such that \(g = qf + r\). Let the numbers such that \(f(n) \mid g(n)\) be \(n_1\), \(n_2\), \(\dots\). Mutliplying \(g = qf + r\) by some big LCM of denominators, we get \(Lg = q'f + r'\), where \(q'\) and \(r'\) are integer polynomials. For \(n_i\), this becomes \[Lkf(n_i) = Lg(n_i) = q'(n_i)f(n_i) + r'(n_i) \implies f(n_i) \mid r'(n_i) \;\; \forall i\] But \(|f(n_i)| > |r'(n_i)|\) for sufficiently large \(i\) due to \(r'\) having lesser degree than \(f\). Thus \(r'(n_i)\) is \(0\) for all large \(i\), implying it (and thus \(r\)) is the zero polynomial.
PFTB deals with this problem in basically the same way but phrases it as: \(\{Lr(n_i)/f(n_i)\} = \{r'(n_i)/f(n_i)\}\) is an integer sequence that converges to \(0\), which means it stabilizes at \(0\) eventually. Note that \(\{r(n_i)/f(n_i)\}\) also converges to \(0\), but since it isn't an integer sequence, that really doesn't mean anything.
Let \(a\), \(b\), \(c\) be integers with \(a \neq 0\) such that \(an^2 + bn + c\) is a perfect square for any positive integer \(n\). Prove that there exist integers \(x\) and \(y\) such that \(a = x^2\), \(b = 2xy\), \(c = y^2\).
Plugging \(n = 0\) implies \(c = y^2\) for some \(y\). \[\left(\sqrt{a} n + \frac{b}{2\sqrt{a}}\right)^2 = an^2 + bn + \frac{b^2}{4a} = x_n^2 - \left(c - \frac{b^2}{4a}\right)\] where \(\{x_i\}\) is the integer sequence \(\sqrt{an^2 + bn + c}\). The sequence \(\{x_n - \sqrt{a} n\}\) is convergent, but not an integer sequence. To obtain a convergent integer sequence from this, we can just notice that \(\{x_{n+1} - x_n\}\) converges to \(\sqrt{a}\), implying \(\sqrt{a}\) is an integer - \(a = x^2\). Now we can say that \(\{x_n - x n\}\) is a convergent integer sequence, so \(x_n = xn + r\) for large \(n\). This means \(ax^2 + bx + c = (xn + r)^2\) for infinitely many \(n\), thus meaning the polynomials are the same, and we are done.
Let \(a_1\), \(a_2\), \(\dots\), \(a_k\) be positive real numbers such that at least one of them is not an integer. Prove that there exist infinitely many positive integers \(n\) such that \(n\) and \(\lfloor a_1 n \rfloor + \lfloor a_2 n \rfloor + \dots + \lfloor a_k n \rfloor \) are relatively prime.
Let \(a_i = \{a_i\}\), so \(0 \le a_i < 1\). Then assuming the contrary we get that \[\frac{\lfloor a_1 p \rfloor + \lfloor a_2 p \rfloor + \dots + \lfloor a_k p\rfloor}{p}\] is an integer sequence for sufficiently large prime \(p\). But how does it behave? Well, it converges to \(a_1 + a_2 + \dots + a_k\), so that must be an integer. Moreover, we get \[\lfloor a_1 p \rfloor + \lfloor a_2 p \rfloor + \dots + \lfloor a_k p\rfloor = a_1p + a_2p + \dots + a_kp \implies a_i p \in \mathbf{Z} \;\; \forall i\] But this is also true for all sufficiently large primes, so this means \(a_i = 0\) for all \(i\), a contradiction to the problem statement.
The above is exactly the solution given in PFTB as well. Indeed, we're starting to get the 2023 N5 vibe. PFTB now says, "Step by step, we start to build some experience in 'guessing' the sequences", which is exactly what I started this for. Peak.
Let \(a\) and \(b\) be integers such that \(a \cdot 2^n + b\) is a perfect square for all positive integers \(n\). Prove that \(a = 0\).
Note that if \(a \cdot 2^n + b\) is a perfect square, then so is \(a \cdot 2^{n+2} + 4b\). But \(a \cdot 2^{n+2} + b\) is also a square. This means the gap between these two squares is \(3b\). Taking \(n\) large, if \(a \neq 0\) then the difference between consecutive squares is unbounded and exceeds \(3b\). Thus \(a = 0\) must hold.
Define a sequence \(\{x_n\}\) such that \(x_n^2 = a \cdot 2^n + b\). The limit of the integer sequence \(\{2x_n - x_{n+2}\}\) as \(n \to \infty\) is \(0\). Thus we must have \(2x_n = x_{n+2}\) for all sufficiently large \(n\), but this means \(b = 0\), which implies \(a\) and \(2a\) are both squares, so \(a = 0\).
A common theme I've noticed is that you basically want the constant term to 'fall off' by only caring about the larger 'degree' things. And the way to only care about the larger degree things is to take \(n \to \infty\).
Let \(a\) and \(b\) be integers greater than \(1\). Prove that there is a multiple of \(a\) which contains all the digits \(0\), \(1\), \(\dots\), \(b - 1\) when written in base \(b\).
Let us look at the number of numbers lesser than \(b^n = (10\dots 0)_b\) written with \(\le b - 1\) digits. Of course, it is \[\binom{b}{1} (b-1)^n + \binom{b}{2} (b-2)^n + \dots + \binom{b}{2} 2^n + \binom{b}{1} 1\]
[problem text]
[problem text]