a_{k+1}= (a_k + a_{k-1})/2 if a_k + a_{k-1} is even ....

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

a_{k+1}= (a_k + a_{k-1})/2 if a_k + a_{k-1} is even ....

G H J

Reveal topic tags

recurrence relation

L

G H BBookmark kLocked kLocked NReply

Source: 2015 Peru MO (ONEM) L3 p4 - finals

The post below has been deleted. Click to close.

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

30628 posts

#1 h Nov 25, 2022, 9:43 PM

Y by

Let $b$ be an odd positive integer. The sequence $a_1, a_2, a_3, a_4$ , is definedin the next way: $a_1$ and $a_2$ are positive integers and for all $k \ge 2$ ,
$a_{k+1}= \begin{cases} \frac{a_k + a_{k-1}}{2} \,\,\, if \,\,\, a_k + a_{k-1} \,\,\, is \,\,\, even \\ \frac{a_k + a_{k-1+b}}{2}\,\,\, if \,\,\, a_k + a_{k-1}\,\,\, is \,\,\,odd\end{cases}$ a) Prove that if $b = 1$ , then after a certain term, the sequence will become constant.
b) For each $b \ge 3$ (odd), prove that there exist values of $a_1$ and $a_2$ for which the sequence will become constant after a certain term.

This post has been edited 1 time. Last edited by parmenides51, Dec 5, 2022, 9:14 PM

Z K Y

The post below has been deleted. Click to close.

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

23452 posts

pco

#2 h Nov 28, 2022, 5:55 PM • 1 Y

Y by Mango247

parmenides51 wrote:

Let $b$ be an odd positive integer. The sequence $a_1, a_2, a_3, a_4$ , is definedin the next way: $a_1$ and $a_2$ are positive integers and for all $k \ge 2$ ,
$a_{k+1}= \begin{cases} \frac{a_k + a_{k-1}}{2} \,\,\, if \,\,\, a_k + a_{k-1} \,\,\, is \,\,\, even \\ \frac{a_k + a_{k-1+b}}{2}\,\,\, if \,\,\, a_k + a_{k-1}\,\,\, is \,\,\,odd\end{cases}$ a) Prove that if $b = 1$ , then after a certain term, the sequence will become constant.

Let $M_k=\max(a_k,a_{k-1})$ and $m_k=\min(a_k,a_{k-1})$
If $a_k+a_{k-1}$ is even, then $M_k\ge m_k$ and we have $a_{k+1}=\frac{M_k+m_k}2\in[m_k,M_k]$
If $a_k+a_{k-1}$ is odd, then $M_k\ge m_k+1$ and we have $a_{k+1}=\frac{M_k+m_k+1}2\in[m_k+1,M_k]$
and so in both cases $M_{k+1}\le M_k$ and $m_{k+1}\ge m_k$
So $M_k$ is convergent with limit $M$ and $m_k$ is convergent with limit $m$
If $m\ne M$ , then sequence $a_k$ ends in $m,M,m,M,m,M,...$ (since $m,m$ or $M,M$ implies $a_k$ constant and so $m=M$
But $(m,M)$ or $(M,m)$ give both the same next $a_k$ , impossible if $m\ne M$

So $m=M$ and sequence $a_k$ ends in constant.

parmenides51 wrote:

b) For each $b \ge 3$ (odd), prove that there exist values of $a_1$ and $a_2$ for which the sequence will become constant after a certain term.

Choose for example $(a_1,a_2)=(1,b+1)$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a