M 7

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 7

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 • 3 Y

Y by UpvoteFarm, Adventure10, Mango247

Prove that the sequence $\{y_{n}\}_{n \ge 1}$ defined by
$y_{0}=1, \; y_{n+1}= \frac{1}{2}\left( 3y_{n}+\sqrt{5y_{n}^{2}-4}\right)$
consists only of integers.

This post has been edited 1 time. Last edited by Peter, Jul 10, 2007, 11:16 PM

Z K Y

The post below has been deleted. Click to close.

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

9 posts

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

Y by UpvoteFarm, Adventure10, Mango247

let $F_0 = 1$ , $F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$ the fibonacci sequence.

is easy to prove, with induction, that $y_n = F_{2n}$

Z K Y

The post below has been deleted. Click to close.

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

1144 posts

Tiks

#3 h May 25, 2007, 12:25 AM • 3 Y

Y by UpvoteFarm, Adventure10, Mango247

Peter wrote:

Prove that the sequence $\{y_{n}\}_{n \ge 1}$ defined by $y_{0}=1, \; y_{n+1}= \frac{1}{2}\left( 3y_{n}+\sqrt{5y_{n}^{2}-4}\right)$ consists only of integers.

I will propose here a different way: without proving any reltion between $y_{n}$ and $F_{n}$ and without using induction

.

So, we have that $2y_{n+1}-3y_{n}=\sqrt{5y_{n}^{2}-1}$ , squaring both sides we get $4y_{n+1}^{2}+9y_{n}^{2}-12y_{n+1}y_{n}=5y_{n}^{2}-4$ , which
gives as $y_{n+1}^{2}+y_{n}^{2}=3y_{n+1}y_{n}-1$ and also $y_{n}^{2}+y_{n-1}^{2}=3y_{n}y_{n-1}-1$ , subtracting from each other we
get $y_{n+1}^{2}-y_{n-1}^{2}=3y_{n}(y_{n+1}-y_{n-1})$ , therefore

$y_{n+1}=3y_{n}-y_{n-1}$

and because $y_{1}$ and $y_{2}$ are integers, then $y_{n}$ is always an integer.

Z K Y

The post below has been deleted. Click to close.

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

91 posts

#4 h Aug 11, 2007, 6:01 AM • 3 Y

Y by Adventure10, UpvoteFarm, Mango247

Peter wrote:

The sequence $\{a_{n}\}_{n \ge 1}$ is defined by
$a_{1}=1, \; a_{n+1}=2a_{n}+\sqrt{3a_{n}^{2}+1}.$
Show that $a_{n}$ is an integer for every $n$ .

Peter wrote:

Prove that the sequence $\{y_{n}\}_{n \ge 1}$ defined by
$y_{0}=1, \; y_{n+1}= \frac{1}{2}\left( 3y_{n}+\sqrt{5y_{n}^{2}-4}\right)$
consists only of integers.

One may establish the following result.

Theorem. Let $u$ , $v$ and $\lambda$ be given integers with $2v \geq \lambda u$ . Suppose that the sequence $\{x_{n}\}_{n \ge 1}$ satisfies the recurrence relation
$x_{n+1}= \frac{{\lambda}x_{n}+\sqrt{ \left({\lambda}^{2}-4 \right){x_{n}}^{2}+4 \left( u^{2}-\lambda uv+v^{2}\right) }}{2}, \;\; n \in \mathbb{N}$
and has the initial condition $x_{1}=u$ . Then, we have $x_{2}=v$ . Also, $\{x_{n}\}_{n \ge 1}$ is the sequence of integers.

Taking $u=1$ and $v=\lambda=2m$ , we get the result also given by Tiks (See M6):

Corollary. Suppose that the sequence $\{x_{n}\}_{n \ge 1}$ satisfies the recurrence relation

\[ x_{n+1}= m x_{n}+\sqrt{ \left({m}^{2}-1 \right){x_{n}}^{2}+1 \right) }, \;\; n \in \mathbb{N}\]

and has the initial condition $x_{1}=1$ . Then, we have $x_{2}=2m$ . Also, $\{x_{n}\}_{n \ge 1}$ is the sequence of integers.

Proof of theorem. First, we give an inductive proof of the fact that the sequence $\{x_{n}\}_{n \ge 1}$ of real numbers is well-defined. The initial term is defined by $x_{1}=u$ . Since
$\left({\lambda}^{2}-4 \right){u}^{2}+4 \left( u^{2}-\lambda uv+v^{2}\right) = \left( 2v-\lambda u \right)^{2}\geq 0,$
we find that
$x_{2}= \frac{{\lambda}u+\sqrt{ \left({\lambda}^{2}-4 \right){u}^{2}+4 \left( u^{2}-\lambda uv+v^{2}\right) }}{2}= \frac{{\lambda}u+\vert 2v-\lambda u \vert }{2}=v$
is well-defined. Now, we fix $n \geq 2$ and suppose that $x_{k}$ is well-defined for all $1 \leq k \leq n$ . To show that $x_{n+1}$ is well-defined, we need to show that
$\left({\lambda}^{2}-4 \right){x_{n}}^{2}+4 \left( u^{2}-\lambda uv+v^{2}\right)$
is nonnegative. By the inductive hypothesis, we obtain
$x_{n}= \frac{{\lambda}x_{n-1}+\sqrt{ \left({\lambda}^{2}-4 \right){x_{n-1}}^{2}+4 \left( u^{2}-\lambda uv+v^{2}\right) }}{2},$
This means that $x_{n}$ is a root of the quadratic equation
$t^{2}-\lambda x_{n-1}t+{x_{n-1}}^{2}-\left( u^{2}-\lambda uv+v^{2}\right) =0$
so that
${x_{n}}^{2}-\lambda x_{n-1}x_{n}+{x_{n-1}}^{2}-\left( u^{2}-\lambda uv+v^{2}\right) =0$
or
$u^{2}-\lambda uv+v^{2}={x_{n}}^{2}-\lambda x_{n-1}x_{n}+{x_{n-1}}^{2}.$
It therefore follows that
$\left({\lambda}^{2}-4 \right){x_{n}}^{2}+4 \left( u^{2}-\lambda uv+v^{2}\right)=\left({\lambda}^{2}-4 \right){x_{n}}^{2}+4 \left({x_{n}}^{2}-\lambda x_{n}x_{n-1}+{x_{n-1}}^{2}\right)$
or
$\left({\lambda}^{2}-4 \right){x_{n}}^{2}+4 \left( u^{2}-\lambda uv+v^{2}\right)= \left( \lambda x_{n}-2 x_{n-1}\right)^{2}\geq 0.$
Now, we prove the main result. We claim that
$x_{n+2}= \lambda x_{n+1}-x_{n}\;\; or \;\; x_{n+2}= x_{n}$
for each $n \in \mathbb{N}$ . Using this claim, one may immediately give an inductive proof of the fact that $x_{n}$ is integer for all $n \in \mathbb{N}$ . To establish the claim, we begin with the recurrence relation
$x_{n+1}= \frac{{\lambda}x_{n}+\sqrt{ \left({\lambda}^{2}-4 \right){x_{n}}^{2}+4 \left( u^{2}-\lambda uv+v^{2}\right) }}{2}.$
We find that $x_{n+1}$ is a root of the quadratic equation
$t^{2}-\lambda x_{n}t+{x_{n}}^{2}-\left( u^{2}-\lambda uv+v^{2}\right) =0$
so that
${x_{n+1}}^{2}-\lambda x_{n}x_{n+1}+{x_{n}}^{2}= \left( u^{2}-\lambda uv+v^{2}\right)$
This means that ${x_{n+1}}^{2}-\lambda x_{n}x_{n+1}+{x_{n}}^{2}$ is constant. It follows that, for all $n \in \mathbb{N}$ ,
${x_{n+2}}^{2}-\lambda x_{n+1}x_{n+2}+{x_{n+1}}^{2}={x_{n+1}}^{2}-\lambda x_{n}x_{n+1}+{x_{n}}^{2}$
so that
${x_{n+2}}^{2}-{x_{n}}^{2}-\lambda x_{n+1}x_{n+2}+\lambda x_{n}x_{n+1}=0$
or
$\left( x_{n+2}-x_{n}\right) \left( x_{n+2}-\lambda x_{n+1}+x_{n}\right)=0.$
This implies that, for each $n \in \mathbb{N}$ , one of the following relations holds:
$x_{n+2}= x_{n}\;\; or \;\; x_{n+2}= \lambda x_{n+1}-x_{n}.$
This completes the proof.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a