Let $f(x)$ be the distance from $x$ to the nearest perfect square. For example, $f(\pi) = 4 - \pi$. Let $\alpha = \frac{3 + \sqrt{5}}{2}$ and let $m$ be an integer such that the sequence $a_n = f(m \; \alpha^n)$ is bounded. Prove that either $m=k^2$ or $m = 5k^2$ for some integer $k$. Proposed by Rodrigo Sanches Angelo (rsa365), Brazil.
Problem
Source: 1st International Mathematical Olympic Revenge
Tags: IMOR, number theory
Rust
22.07.2017 22:18
Let $q_1=\frac{1+\sqrt{5}}{2}, q_2=\frac{1-\sqrt{5}}{2}$. Then $\alpha^n=q_1^{2n}$ and $q_1^n+q_2^n=L_n, q_1^n-q_2^n=\sqrt 5 F_n$. Therefore $f(k^2\alpha^n)=|k^2L_n^2-k^2\alpha^n|\le k^2(2+q_2^n)<3k^2$ bounded, $f(5k^2\alpha^n)=k^2 *25(2+q_2^n)<75 k^2$ - bounded too. For other cases nearest perfect square is square of nearest integer $\sqrt m Ln$ or nearest integer $\sqrt{5m}F_n$ and $a_n=f(m\alpha^n)$ is not bounded.
rsa365
22.07.2017 22:47
This is a proof of the converse of the problem (that the sequence is indeed bounded for m = k^2 or 5k^2), but it looks like you have not argued for why the sequence is not bounded in the other cases.
DVDthe1st
24.07.2017 14:14
What a delightful problem!
Note that $\alpha = \varphi^2$, and we write $a_n \sim b_n$ if $\lim_{n\rightarrow \infty} (a_n-b_n)=0$
Suppose $l_n$ is a integer sequence such that $|m\varphi^{2n}-l_n^2|<C$ for a fixed $C$ throughout. Then it is clear that $l_n\sim \sqrt{m}\varphi^{n}$.
Hence $l_{n+2}\sim l_n+l_{n+1}$, but since $l_n$ is an integer sequence thus $l_{n+2}=l_{n+1}+l_n$ for all sufficiently large $n$. Note that $l_n=aF_{n}+bF_{n-1}$, where $a,b$ are integers and $F_n$ is the Fibonnaci sequence ($1,1,2,3,5,...$). Hence $l_{n}\sim \frac{a\varphi +b}{\sqrt{5}}\cdot \varphi^n\sim \sqrt{m}\varphi^n$, so $\frac{a\varphi +b}{\sqrt{5}}=\sqrt{m}$ and so it is clear (by linear independence of radicals over $\mathbb{Q}$) that $\sqrt{m}$ is either an integer or an integer multiple of $\sqrt{5}$.
i707107
18.03.2019 01:04
@DVDthe1st The step from "integer sequence $l_n$ satisfies $l_{n+2}\sim l_n+l_{n+1}$" to "$l_{n+2}=l_{n+1}+l_n$ for all sufficiently large $n$" seems to have a counterexample. For, let $l_n$ be an integer sequence defined by the recurrence $l_{n+2}=l_n+l_{n+1}+1+(-1)^n$.
fattypiggy123
18.03.2019 03:13
@above: For $n$ even, you have $l_{n+2} - l_{n+1} - l_n = 2$ so it doesn't satisfy $\lim_{n \to \infty} (l_{n+2} - l_{n+1} - l_n) = 0$.
i707107
18.03.2019 03:16
Maybe the notation $\sim$ needs to be defined to avoid misunderstanding. It means more commonly that $a_n\sim b_n$ if $a_n/b_n \rightarrow 1$.
fattypiggy123
18.03.2019 03:21
It is defined on the first line of the solution though... Edit: Although I would admit I thought the same as you at first
i707107
18.03.2019 04:36
I see. I couldn't believe that I missed the first line..