Prove that all the terms of the sequence are integral

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Prove that all the terms of the sequence are integral

G H J

Reveal topic tags

algebra unsolved

L

G H BBookmark kLocked kLocked NReply

Source: CWMO 2003, Problem 5

The post below has been deleted. Click to close.

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

3647 posts

orl

#1 h Dec 27, 2008, 1:12 AM • 2 Y

Y by Adventure10, Mango247

The sequence $\{a_n\}$ satisfies $a_0 = 0, a_{n + 1} = ka_n + \sqrt {(k^2 - 1)a_n^2 + 1}, n = 0, 1, 2, \ldots$ , where $k$ is a fixed positive integer. Prove that all the terms of the sequence are integral and that $2k$ divides $a_{2n}, n = 0, 1, 2, \ldots$ .

Z K Y

The post below has been deleted. Click to close.

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

520 posts

#2 h Dec 27, 2008, 3:12 AM • 2 Y

Y by Adventure10, Mango247

It is easy to prove, by induction
$a_{n+1}=2ka_n-a_{n-1}$ and $a_{n+1}a_{n-1}+1=a_n^2$ .
Then it is easy to verify the modulo of $2k$ is $0,1,0,-1,0,1,0,-1,...$ .

Z K Y

The post below has been deleted. Click to close.

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

6194 posts

#3 h Dec 27, 2008, 6:29 AM • 2 Y

Y by Adventure10, Mango247

This is standard...If you rearrange and square it, you get

$a_{n+1}^2-2ka_na_{n+1}+k^2a_n^2=(k^2-1)a_n^2+1$

Then $a_{n+1}^2-2ka_n(a_{n+1})+a_n^2-1=0$

Note that $x^2-2ka_n x+a_n^2-1=0$ has roots $a_{n+1}$ , $a_{n-1}$ the function is increasing so $a_{n+1}>a_n>a_{n-1}$ so $a_{n+1}\ne a_{n-1}$ so they are the distinct roots of that quadratic and so

$x_1+x_2=2ka_n$ which gives that nice recursion. The rest of the problem is then trivial by induction.

Z K Y

The post below has been deleted. Click to close.

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

386 posts

#4 h Apr 5, 2020, 4:49 PM

Y by

So rearrange the condition a little bit and square it we get $a_{n+1}^2-2ka_na_{n+1}+a_n^2-1=0$
We express $a_{n+1}^2 = 2ka_na_{n+1}-a_n^2+1$
So now let $n \rightarrow n+1$ , we have the following:
$a_{n+2}^2-2ka_{n+1}a_{n+2}+a_{n+1}^2-1=0$ Plugging in the definition of $a_{n+1}^2$ we get
$(a_{n+2}-a_n)(a_{n+2}+a_n-2ka_{n+1})=0$ Because the sequence $\{a_n\}$ is increasing we have the following:
$a_{n+2}+a_{n}=2ka_{n+1}$
We can calculate $a_1=1$
So now by induction we see that $\{a_n\}$ is a subsequnce of $\mathbb{Z}$
Since $2k | a_n + a_{n+2}$ and since $2k|a_0$ .By induction with a step of 2 we get that $2k|a_{2n}$ , $\forall n \in \mathbb{N}_0$

This post has been edited 1 time. Last edited by EulersTurban, Apr 6, 2020, 9:36 AM
Reason: LaTeX stuff

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a