Define sequence $\{a_{n}\}$,such $$a_{1}=1,a_{2}=2,a_{k+2}=2a_{k+1}+a_{k},k\ge 1$$

Find all positive real number $\beta$,such only have a finite number of relatively prime integers $(p,q)$ such that $$\left|\dfrac{p}{q}-\sqrt{2}\right|<\dfrac{\beta}{q^2}$$ and there can't exsit $n$ such $q=a_{n}$

and this problem is Germany National Olympiad 2013 last problem (2), see: http://www.mathematik-olympiaden.de/aufgaben/52/4/A52124b.pdf

My try: since $$ a_{n+2}=2a_{n+1}+a_{n}\Longrightarrow r^2=2r+1\Longrightarrow r_{1}=\sqrt{2}+1,r_{2}=1-\sqrt{2}$$ so $$a_{n}=A(1+\sqrt{2})^{n-1}+B(1-\sqrt{2})^{n-1},a_{1}=1,a_{2}=2$$ so $$A+B=1,A(1+\sqrt{2})+B(1-\sqrt{2})=2\Longrightarrow A=\dfrac{2+\sqrt{2}}{4},B=\dfrac{2-\sqrt{2}}{4}$$ so $$a_{n}=\dfrac{2+\sqrt{2}}{4}(1+\sqrt{2})^n+\dfrac{2-\sqrt{2}}{4}(1-\sqrt{2})^n$$ so there can't postive integer $n$,such $q=a_{n}$

other hand $$\left|\frac{p}{q}-\sqrt{2}\right| = \frac{|p^2-2q^2|}{q^2\left|\frac{p}{q} + \sqrt{2}\right|}$$ Now we can't use the pell equation,because this problem is finite number of relatively prime integers $(p,q)$

so how solve it?

I have read this solution,It's Nice: How find the value $\beta$ such $\left|\frac{p}{q}-\sqrt{2}\right|<\frac{\beta}{q^2}$

I think we can find other methods to solve this problem?

This is different problem

I don't know why,and it is said china all can't comment.maybe this post explain why?so I have say in there http://meta.math.stackexchange.com/questions/16661/mse-requires-javascript-from-another-domain-which-is-blocked-or-failed-to-load

  • 7
    $\begingroup$ How you can fail to link this to math.stackexchange.com/q/915540 and to the substantial information you received there, escapes me... $\endgroup$ – Did Sep 1 '14 at 7:02
  • 3
    $\begingroup$ Why can't you comment? $\endgroup$ – Did Sep 1 '14 at 7:12
  • 1
    $\begingroup$ I would guess that excluding the $a_n$:s means that $|p^2-2q^2|\ge2$. If correct proving it should not be too difficult (basically you need to show that all the solutions of the Pell equation have $q=a_n$ for some $n$). Using the theory of units of rings of integers of real quadratic extensions of $\Bbb{Q}$ leads to it, but that is probably not an allowed piece of theory. I would try "infinite descent" (or induction): if $p_n^2-2q_n^2=1$, then multiplying $(p_n-q_n\sqrt2)$ by $(\sqrt2 +1)$ gives a "smaller" solution. I'm off air, so cannot pursue this now. $\endgroup$ – Jyrki Lahtonen Sep 1 '14 at 7:46
  • $\begingroup$ Jyrki's comment above has the right idea. If you can prove this then take $p,q$ s.t. $|p^2 - 2q^2| = 2$ and show that you have an infinite number of solutions for $\beta \geq \frac{1}{\sqrt{2}}$. Now assume you also have infinite number of solutions for $\beta < \frac{1}{\sqrt{2}}$ and derive a contradiction. $\endgroup$ – Winther Sep 8 '14 at 17:18

According to your computations, $$ \left|\frac{p}{q}-\sqrt2\right| = \frac{\left|\frac{p^2}{q^2}-\sqrt2^2\right|}{\frac{p}{q}+\sqrt2} = \frac1{q^2}\cdot\frac{|p^2-2q^2|}{2\sqrt2+\Big(\frac{p}{q}-\sqrt2\Big)}. $$

The condition $q\ne a_n$ excludes the solutions of the Pellian equation $p^2-2q^2=\pm1$. But allows $p^2-2q^2=2$.

I. First we show that there are only finitely many good pairs $(p,q)$ for $\beta<\frac1{\sqrt2}$.

Suppose that $\beta<\frac1{\sqrt2}$, and let $\varepsilon=\frac2\beta-2\sqrt2$. Consider a good pair $(p,q)$. If $q>\sqrt{\beta/\varepsilon}$ then $|\frac{p}{q}-\sqrt2|\le \frac{\beta}{q^2}<\varepsilon$, and thus $$ \frac\beta{q^2} \ge \left|\frac{p}{q}-\sqrt2\right| \ge \frac1{q^2}\cdot\frac{|p^2-2q^2|}{2\sqrt2+\Big|\frac{p}{q}-\sqrt2\Big|} > \frac1{q^2}\cdot\frac2{2\sqrt2+\varepsilon} = \frac\beta{q^2}, $$ contradiction. Hence, the set of possible values $q$ is bounded by $\sqrt{\beta/\varepsilon}$ and thus finite.

II. Now we construct infinitely many good pairs ($p,q)$ for $\beta\ge\frac1{\sqrt2}$.

The Pellian equation $p^2-2q^2=2$ has infinitely many solutions; for such pairs $\frac{p}{q}>\sqrt2$, so $$ \left|\frac{p}{q}-\sqrt2\right| = \frac1{q^2}\cdot\frac{|p^2-2q^2|}{2\sqrt2+\Big(\frac{p}{q}-\sqrt2\Big)} < \frac1{q^2}\cdot\frac2{2\sqrt2+0} \le \frac\beta{q^2}. $$

Therefore, the answer is $\beta\in\left(0,\frac1{\sqrt2}\right)$.


Not a complete answer, but I will show that if $(p,q)$ are solution to $|p^2 - 2q^2| = 1$ then $q = a_n$ for some $n$ (as Jyrki said in the comments).

The fundamental solution of the Pell equation $|p^2 - 2q^2| = 1$ is $(p,q) = (1,1)$. All the other solutions can therefore be written on the form

$$p_m + q_m \sqrt{2} = (\sqrt{2} + 1)^m$$

From this we can extract a recursion formula for $(p_m,q_m)$. We have

$$p_{m+1} + q_{m+1} \sqrt{2} = (\sqrt{2} + 1)(p_{m}+ q_{m} \sqrt{2})$$

Multiplying out and using that since $p_m,q_m$ are integers and $\sqrt{2}$ irrational ($A_n + \sqrt{2}B_n = 0 \implies A_n=B_n=0$ if $A_n,B_n$ are integers) then

$$p_{m+1} - p_m = 2q_m$$ $$q_{m+1} - q_{m} = p_{m}$$

Using $(q_{m+2} - q_{m+1}) - (q_{m+1} - q_{m}) = p_{m+1}-p_m = 2q_n$ we can eliminate $p_m$ to get a recursion realation for $q_m$ only

$$q_{m+2} = 2q_{m+1} + q_m$$

which is the same equation as for $a_n$. From $q_1 = p_1 = 1$ we get $q_2 = 2$ so the initial conditions are also the same.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.