Suppose $N\in \mathbb N$ is not a perfect square, hence we know that the continued fraction of $\sqrt{N}$ is of the form $\sqrt{N}=[a_0,\overline{a_1,a_2,...,a_n}]$. If $a_1\neq 1$ prove that $a_i\le 2a_0$.
Problem
Source: Iran 3rd round 2012-Algebra exam-P2
Tags: inequalities, continued fraction, algebra proposed, algebra
16.02.2019 23:41
Bump
17.02.2019 21:06
So, we have $\sqrt{N}= a_0+\frac{1}{\alpha_0}$, where $a_0=\lfloor \sqrt{N}\rfloor$ and further: $$\alpha_i = a_{i+1}+\frac{1}{\alpha_{i+1}}\,,\,i=0,1,\dots$$It's easy to show by induction that: $$\alpha_i =\frac{p_i+\sqrt{N}}{q_i}; i=0,1,\dots$$where $p_i,q_i\in\mathbb{N}$ and moreover $$(1)\,\,\,\,\,\,\,\,\,\, -1<\frac{p_i-\sqrt{N}}{q_i}<0\,;\, i=0,1,\dots$$Denote $\xi_i=\frac{p_i-\sqrt{N}}{q_i}$ hence $p_i=\xi_i q_i+\sqrt{N}$. Let us estimate $a_{i+1}=\lfloor \alpha_i\rfloor $. We have: $$\alpha_i= \frac{p_i+\sqrt{N}}{q_i}=\frac{\xi q_i+2\sqrt{N}}{q_i}=\xi_i + \frac{2\sqrt{N}}{q_i} $$In the case $q_i\geq 2$, we have $a_{i+1}=\lfloor \alpha_i\rfloor \leq \lfloor \sqrt{N}\rfloor=a_0$, since $\xi<0$. Now, consider the case $q_i=1$. $$\alpha_i = p_i+\sqrt{N}\,;\, i\in\mathbb{Z}_{\geq 0}$$ By $(1)$, it follows $-1<p_i-\sqrt{N}<0$, which means $p_i=\lfloor\sqrt{N}\rfloor$ and hereby $$a_{i+1}=\lfloor \alpha_i\rfloor =2\lfloor \sqrt{N}\rfloor=2a_0$$ Remark. In the last case it's easy to see that $a_{i+1}=2a_0$ is the last term of the period and the next terms are again $a_1,a_2,\dots$, that's $\sqrt{N}=[a_0,\overline{a_1,a_2,...,a_{n-1},2a_0}]$. If one knows the usual proof the continued fraction of $\sqrt{N}$ is periodic, there is a big chance to solve the problem. The above proof is based on it. It just remains to show that $p_i,q_i\in\mathbb{N}$ that satisfy $(1)$ are only finitely many.