M 29

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

M 29

G H J

Reveal topic tags

Recursive Sequences

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:25 AM • 2 Y

Y by Adventure10, Mango247

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#2 h Jul 19, 2007, 11:59 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

345 posts

#3 h Oct 18, 2008, 7:32 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2349 posts

#4 h Oct 18, 2008, 9:35 PM • 2 Y

Y by Adventure10, Mango247

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.

sidenote

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a