Peter wrote: The sequence $ \{a_{n}\}_{n \ge 1}$ is defined by $ a_{1}=1$ and \[ a_{n+1}= \frac{a_{n}}{2}+\frac{1}{4a_{n}}\; (n \in \mathbb{N}).\] Prove that $ \sqrt{\frac{2}{2a_{n}^{2}-1}}$ is a positive integer for $ n>1$. I find such problems beautiful, but unfortunately their solutions use to consist mostly of computation... First, it is clear by induction that $ a_{n}\in\mathbb{Q}$ and $ a_{n}>0$ for every $ n\in\mathbb{N}$. Hence, for every $ n\in\mathbb{N}$, we have $ \frac{a_{n}}{2}\neq\frac{1}{4a_{n}}$ (in fact, $ \frac{a_{n}}{2}=\frac{1}{4a_{n}}$ would lead to $ a_{n}^{2}=\frac{1}{2}$, but this is impossible since $ a_{n}\in\mathbb{Q}$, and $ \frac{1}{2}$ is not a square of a rational number), so that $ \frac{a_{n}}{2}-\frac{1}{4a_{n}}\neq0$ and thus (1) $ \left( \frac{a_{n}}{2}-\frac{1}{4a_{n}}\right)^{2}>0$ for every $ n\in\mathbb{N}$. Further, (2) $ 2a_{n}^{2}-1>0$ for every $ n\in\mathbb{N}$. In fact, for $ n=1$, this is clear since $ 2a_{1}^{2}-1=2\cdot1^{2}-1=1>0$, and for $ n>1$, this follows from $ 2a_{n}^{2}-1=2\left( \frac{a_{n-1}}{2}+\frac{1}{4a_{n-1}}\right)^{2}-1=2\left( \frac{a_{n-1}}{2}-\frac{1}{4a_{n-1}}\right)^{2}>0$ (the last step used $ \left( \frac{a_{n-1}}{2}-\frac{1}{4a_{n-1}}\right)^{2}>0$, what follows from (1)). Now, set $ b_{n}=\sqrt{\frac{2}{2a_{n}^{2}-1}}$ for every $ n\in\mathbb{N}$. Note that $ b_{n}$ is well-defined since $ \frac{2}{2a_{n}^{2}-1}>0$ (what is because $ 2a_{n}^{2}-1>0$, as proven in (2)). The crux of the solution is to prove that (3) $ b_{n+1}=2b_{n}\left( 1+b_{n-1}^{2}\right)$ for every integer $ n>1$. Before we show this, we need two more lemmata. First, we prove that (4) $ b_{n+1}=\frac{4a_{n}}{2a_{n}^{2}-1}$ for every $ n\in\mathbb{N}$. In fact, $ b_{n+1}=\sqrt{\frac{2}{2a_{n+1}^{2}-1}}=\sqrt{\frac{2}{2\left(\frac{a_{n}}{2}+\frac{1}{4a_{n}}\right)^{2}-1}}=\sqrt{\frac{2}{2\left(\frac{a_{n}}{2}-\frac{1}{4a_{n}}\right)^{2}}}$ $ =\sqrt{\frac{1}{\left( \frac{a_{n}}{2}-\frac{1}{4a_{n}}\right)^{2}}}=\frac{1}{\left\vert \frac{a_{n}}{2}-\frac{1}{4a_{n}}\right\vert }=\frac{1}{\left\vert \frac{2a_{n}^{2}-1}{4a_{n}}\right\vert }=\frac{4\left\vert a_{n}\right\vert }{\left\vert 2a_{n}^{2}-1\right\vert }$, and since $ a_{n}>0$ and $ 2a_{n}^{2}-1>0$ (the latter according to (2)), we have $ \left\vert a_{n}\right\vert =a_{n}$ and $ \left\vert 2a_{n}^{2}-1\right\vert =2a_{n}^{2}-1$ and thus $ b_{n+1}=\frac{4\left\vert a_{n}\right\vert }{\left\vert 2a_{n}^{2}-1\right\vert }=\frac{4a_{n}}{2a_{n}^{2}-1}$, so that (4) is proven. Now we show that (5) $ b_{n+1}=\frac{8a_{n-1}\left( 2a_{n-1}^{2}+1\right) }{\left( 2a_{n-1}^{2}-1\right)^{2}}$ for every integer $ n>1$. In fact, (4) yields $ b_{n+1}=\frac{4a_{n}}{2a_{n}^{2}-1}=\frac{4\left( \frac{a_{n-1}}{2}+\frac{1}{4a_{n-1}}\right) }{2\left( \frac{a_{n-1}}{2}+\frac{1}{4a_{n-1}}\right)^{2}-1}=\frac{4\left( \frac{a_{n-1}}{2}+\frac{1}{4a_{n-1}}\right) }{2\left( \frac{a_{n-1}}{2}-\frac{1}{4a_{n-1}}\right)^{2}}$ $ =\frac{4\frac{2a_{n-1}^{2}+1}{4a_{n-1}}}{2\left( \frac{2a_{n-1}^{2}-1}{4a_{n-1}}\right)^{2}}=\frac{8a_{n-1}\left( 2a_{n-1}^{2}+1\right)}{\left( 2a_{n-1}^{2}-1\right)^{2}}$. Now, let $ n>1$ be an integer. Then, - (4) yields $ b_{n}=\frac{4a_{n-1}}{2a_{n-1}^{2}-1}$ (since $ n-1\in\mathbb{N}$); - (5) yields $ b_{n+1}=\frac{8a_{n-1}\left( 2a_{n-1}^{2}+1\right) }{\left( 2a_{n-1}^{2}-1\right)^{2}}$; - the definition of $ b_{n-1}$, namely $ b_{n-1}=\sqrt{\frac{2}{2a_{n-1}^{2}-1}}$, yields $ b_{n-1}^{2}=\frac{2}{2a_{n-1}^{2}-1}$. Hence, $ 2b_{n}\left( 1+b_{n-1}^{2}\right) =2\cdot\frac{4a_{n-1}}{2a_{n-1}^{2}-1}\cdot\left( 1+\frac{2}{2a_{n-1}^{2}-1}\right)$ $ =\frac{8a_{n-1}}{2a_{n-1}^{2}-1}\cdot\frac{2a_{n-1}^{2}+1}{2a_{n-1}^{2}-1}=\frac{8a_{n-1}\left( 2a_{n-1}^{2}+1\right) }{\left( 2a_{n-1}^{2}-1\right)^{2}}=b_{n+1}$, so that (3) is proven. The rest is obvious: First, $ a_{1}=1$ yields $ b_{1}=\sqrt{\frac{2}{2a_{1}^{2}-1}}=\sqrt{\frac{2}{2\cdot1^{2}-1}}=\sqrt{2}$, so that $ b_{1}^{2}=2$. Then, application of (4) to $ n=1$ yields $ b_{2}=\frac{4a_{1}}{2a_{1}^{2}-1}=\frac{4\cdot1}{2\cdot1^{2}-1}=4$. Besides, application of (3) to $ n=2$ yields $ b_{3}=2b_{2}\left( 1+b_{1}^{2}\right) =2\cdot4\cdot\left( 1+2\right) =24$. Thus, $ b_{2}=4$ and $ b_{3}=24$ are positive integers. Using the recursive equation (3) for the sequence $ \left( b_{i}\right)_{i>1}$, it thus follows by induction that $ b_{n}$ is a positive integer for every integer $ n>1$. Since $ b_{n}=\sqrt{\frac{2}{2a_{n}^{2}-1}}$, this means that $ \sqrt{\frac{2}{2a_{n}^{2}-1}}$ is a positive integer for every integer $ n>1$. Problem solved.

A much shorter solution- Substitute $ b_n = 2a_n$. The recursion becomes $ b_{n + 1} = \frac {b_{n}}{2} + \frac {1}{b_{n}}, b_{1} = 2$. Let $ b_{n} = \frac {p_n}{q_n}$. Notice that: $ b_{n + 1} = \frac {p_{n + 1}}{q_{n + 1}} = \frac {p_{n}^2 + 2q_{n}^2}{2p_{n}q_{n}}$ The sequences $ p_n, q_n$ are not usually determined uniquely, but we will set them to follow the following recursion, and thus they will be unique: $ p_{n + 1} = p_{n}^2 + 2q_{n}^2, q_{n + 1} = 2p_{n}q_{n}, p_{1} = \sqrt {2}, q_{1} = \frac {\sqrt {2}}{2}$ Notice that: $ p_{n + 1}^2 - 2q_{n + 1}^2 = (p_{n}^2 + 2q_{n}^2)^2 - 8p_{n}q_{n} = (p_{n}^2 - 2q_{n}^2)^2$ $ \implies p_{n}^2 - 2q_{n}^2 = (p_{1}^2 - 2q_{1}^2)^{2^{n - 1}} = 1$ Also, note that $ p_n, q_n$ are positive integers for n>1: $ p_{2} = 2 + 2\cdot 0.5 = 3, q_{2} = 2\sqrt {2}\frac {\sqrt {2}}{2} = 2$, and our claim follows immediately from induction. Now: $ \sqrt {\frac {2}{2a_{n}^{2} - 1}} = \frac {2q_{n}}{\sqrt {p_{n}^2 - 2q_{n}^2}} = 2q_{n}$. Q.E.D. It is also possible to show that $ (p_n,q_n)$ generates a subset of the solutions to Pell's Equation $ x^2 - 2y^2 = 1$, and find the explicit formula for $ a_{n}$: $ p_{n} = \frac {(1 + \sqrt {2})^{2^{n - 1}} + (1 - \sqrt {2})^{2^{n - 1}}}{2}$, for n>1 $ q_{n} = \frac {(1 + \sqrt {2})^{2^{n - 1}} - (1 - \sqrt {2})^{2^{n - 1}}}{2\sqrt {2}}$, for n>1 $ a_{n} = \frac {p_{n}}{2q_{n}} = \frac {\sqrt {2}}{2}\frac {(1 + \sqrt {2})^{2^{n - 1}} + (1 - \sqrt {2})^{2^{n - 1}}}{(1 + \sqrt {2})^{2^{n - 1}} - (1 - \sqrt {2})^{2^{n - 1}}}$, for n>1 $ \sqrt {\frac {2}{2a_{n}^{2} - 1}} = 2q_{n} = \frac {(1 + \sqrt {2})^{2^{n - 1}} - (1 - \sqrt {2})^{2^{n - 1}}}{\sqrt {2}}$ The motivation is this - $ p_{n+1}\pm\sqrt{2}q_{n+1}=(p_{n}\pm\sqrt{2}q_{n})^2 \implies p_{n}\pm\sqrt{2}q_{n}=(p_{1}\pm\sqrt{2}q_{1})^{2^{n-1}}$, or: $ p_{n}+\sqrt{2}q_{n}=(\sqrt{2}+1)^{2^{n-1}}, p_{n}-\sqrt{2}q_{n}=(\sqrt{2}-1)^{2^{n-1}}$ Summing\subtracting (and dividing by the appropriate constant) gives the formulas above.

bambaman wrote: Substitute $ b_n = 2a_n$. The recursion becomes $ b_{n + 1} = \frac {b_{n}}{2} + \frac {1}{b_{n}}, b_{1} = 2$. Let \[ x = 1 + \sqrt {2}\qquad s_n = \sqrt{2}\frac {x^n + x^{ - n}}{x^n - x^{ - n}} \] Then \[ \frac {s_n}{2} + \frac {1}{s_n} = \frac {\sqrt {2}}{2}\left(\frac {x^n + x^{ - n}}{x^n - x^{ - n}} + \frac {x^n - x^{ - n}}{x^n + x^{ - n}}\right) = \frac {\sqrt {2}}{2}\frac {2(x^{2n} + x^{ - 2n})}{x^{2n} - x^{ - 2n}} = s_{2n} \] as $ s_1=2$ we have $ b_n = s_{2^{n-1}}$. Then \[ \sqrt {\frac {2}{2a_n^2 - 1}} = \sqrt {\frac {4}{b_n^2 - 2}} = \frac{x^{2^{n-1}} - x^{ - 2^{n-1}}}{\sqrt{2}} \] which is clearly an integer by the binomial theorem.