Can this sequence be bounded?

The post below has been deleted. Click to close.

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

darij grinberg

6555 posts

darij grinberg

#1 h Jan 19, 2005, 11:00 AM • 8 Y

Y by Davi-8191, Adventure10, jhu08, megarnie, HWenslawski, ImSh95, Mango247, and 1 other user

Let $a_0$ , $a_1$ , $a_2$ , ... be an infinite sequence of real numbers satisfying the equation $a_n=\left|a_{n+1}-a_{n+2}\right|$ for all $n\geq 0$ , where $a_0$ and $a_1$ are two different positive reals.

Can this sequence $a_0$ , $a_1$ , $a_2$ , ... be bounded?

Proposed by Mihai Bălună, Romania

This post has been edited 1 time. Last edited by djmathman, Sep 27, 2015, 2:12 PM

Z K Y

The post below has been deleted. Click to close.

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

Valentin Vornicu

7301 posts

Valentin Vornicu

#2 h Jan 19, 2005, 8:51 PM • 6 Y

Y by jhu08, megarnie, Adventure10, AlphaBetaGammaOmega, ImSh95, Mango247

Yes, actually this is a Romanian proposal by Mihai Bălună. Have fun with this nice problem.

Z K Y

The post below has been deleted. Click to close.

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

Peter Scholze

644 posts

Peter Scholze

#3 h Jan 20, 2005, 3:44 PM • 5 Y

Y by Adventure10, jhu08, megarnie, ImSh95, Mango247

? yes?
there are thousands of proofs given(in particular, by darij and me), that this sequence is always unbounded.

Z K Y

The post below has been deleted. Click to close.

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

darij grinberg

6555 posts

darij grinberg

#4 h Jan 20, 2005, 4:57 PM • 4 Y

Y by jhu08, Adventure10, ImSh95, Mango247

Well, it's not exactly that I didn't give a proof, but it wasn't quite correct either... So, the problem is not too trivial...

darij

Z K Y

The post below has been deleted. Click to close.

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

zhaobin

2382 posts

zhaobin

#5 h Jan 22, 2005, 12:10 PM • 4 Y

Y by Adventure10, jhu08, ImSh95, Mango247

I think a_i must be position.

BTW,I am intrested in this problem.can you post the solution.

Z K Y

The post below has been deleted. Click to close.

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

Xell

40 posts

Xell

#6 h Jan 25, 2005, 1:04 AM • 4 Y

Y by Adventure10, jhu08, ImSh95, Mango247

First, some basic facts: all the terms of the sequence are positive, two consecutive terms are always different, we have $u_{n+2}=u_{n+1}-u_{n}$ or $u_{n+2}=u_{n+1}+u_{n}$ , but if $u_{n}>u_{n+1}$ , then necessarily, $u_{n+2}=u_{n+1}+u_{n}$ .

I will then prove the following result: if $u_{n}<u_{n+1}$ for some integer n, then for some $m>n$ we have $u_{n+1}<u_{m}$ and $u_{n}+u_{n+1} < u_{m+1}$ .

Property 1: let a,b be two positive real numbers with $a<b$ and suppose that $u_{n}=b-a$ , $u_{n+1}=2kb-(2k-1)a$ for some integer k>0. If $u_{n+2}=u_{n+1}-u_{n}$ then we have $u_{n+2}<u_{n+1}$ so, from a previous remark, we have necessarily, $u_{n+3}=u_{n+1}+u_{n+2}$ . We check that in that case, $u_{n+2}>b$ and $u_{n+3}>a+b$ .

Property 2: let a,b be two positive real numbers with $a<b$ and suppose that $u_{n}=2kb-(2k-1)a$ , $u_{n+1}=(2k+1)b-2ka$ for some integer k>0. If $u_{n+2}=u_{n+1}+u_{n}$ , then We check that $u_{n+1}> b$ and $u_{n+2}> a+b$ .

Suppose now that $a=u_{n}<u_{n+1}=b$ . If $u_{n+2}=a+b$ , the result is proved. So suppose that $u_{n+2}=b-a$ . Then necessarily, $u_{n+3}=u_{n+2}+u_{n+1}=2b-a$ . Property 1 (with k=1) shows that the result is proved if $u_{n+4}=u_{n+3}-u_{n+2}$ , so suppose that $u_{n+4}=u_{n+3}+u_{n+2}=3b-2a$ . Property 2 (with k=1) proves the result if $u_{n+5}=u_{n+4}+u_{n+3}$ so suppose that $u_{n+5}=u_{n+4}-u_{n+3}=b-a$ . $u_{n+4}>u_{n+5}$ , so $u_{n+6}=u_{n+5}+u_{n+4}=4b-3a$ . And so on (= induction) we show that the result is proved by using property 1 and 2 unless we have the following sequence:
a,b,b-a,2b-a,3b-2a,b-a,4b-3a,5b-4a,...,b-a,2kb-(2k-1)a,(2k+1)b-2ka,b-a,...
But in that last case, 2kb-(2k-1)a, can be as high as we want, for example higher than b, and (2k+1)b-2ka higher than a+b.
The result is therefore proved.

Now, there are always consecutive terms such that $u_{n}<u_{n+1}$ (if $u_{n}>u_{n+1}$ for some n, then $u_{n+2}=u_{n}+u_{n+1}>u_{n+1}$ ). Name $a=u_{n}<u_{n+1}=b$ . Then an easy induction using the result shows that one can find terms higher than $k(a+b)$ for every integer k, which shows that such a sequence can not be bounded.

Z K Y

The post below has been deleted. Click to close.

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

k2c901_1

146 posts

k2c901_1

#7 h Aug 12, 2005, 8:44 AM • 3 Y

Y by Adventure10, jhu08, ImSh95

This problem was used as problem 1 of the final exam of the 3rd TST of Taiwan 2005.

Z K Y

The post below has been deleted. Click to close.

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

indybar

398 posts

indybar

#8 h Aug 13, 2005, 5:20 AM • 5 Y

Y by ultralako, Adventure10, jhu08, ImSh95, Mango247

I'm not really clear with Xell's solution. Can anybody elaborate?

Z K Y

The post below has been deleted. Click to close.

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

bomb

365 posts

bomb

#9 h Aug 13, 2005, 6:22 AM • 3 Y

Y by Adventure10, jhu08, ImSh95

Wasnt this posted before???

Bomb

Z K Y

The post below has been deleted. Click to close.

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

Philip_Leszczynski

327 posts

Philip_Leszczynski

#10 h Dec 12, 2005, 12:17 AM • 4 Y

Y by Adventure10, jhu08, ImSh95, Mango247

Since $a_n = |a_{n+1}-a_{n+2}|$ , we see that all elements of $\{a_n\}$ are nonnegative.
We first show that all elements of $\{a_n\}$ are positive.

Suppose for the sake of contradiction that there exists an $i \ge 0$ such that $a_{i+2}=0$ .
(Obviously $a_0,a_1 \ne 0$ since this is given.)
$a_i = |a_{i+1} - a_{i+2}|$ , so $a_i = a_{i+1}$ . Let $x=a_i=a_{i+1}$ .
We will show that for any $j \ge 0$ , the set $\{a_k|j \le k \le i_1 \}$ has only two distinct elements: $x$ and $0$ .
For the base case we have $j=i$ . We will induct backwards on $j$ , from $i$ to $0$ .
By the inductive hypothesis, $a_{j+1} \epsilon \{0,x\}$ , $a_{j+2} \epsilon \{0,x\}$ .
Since $a_j = |a_{j+1} - a_{j+2}|$ , $a_j \epsilon \{|0-0|,|0-x|,|x-0|,|x-x|\} = \{0,x\}$ .
(Remember that $x$ is nonnegative.)
This completes the induction. So $a_0 \epsilon \{0,x\}$ and $a_1 \epsilon \{0,x\}$ .
Since we are given that $a_0$ and $a_1$ are positive, $a_0=a_1=x$ . (If $x=0$ , then we have our contradiction.)
But we are also given that $a_0$ and $a_1$ are different, so we have our contradiction.
Therefore, all elements of $\{a_n\}$ are positive, and as a corollary, no two consecutive elements of $\{a_n\}$ are equal.

We will now show that $a_0$ cannot be the largest element of $\{a_n\}$ .
Suppose for the sake of contradiction that it is.
Let $a_0 = x/k$ , and let $a_1 = 1/k$ . Then $k>0$ and $x>1$ .
$ka_0 = x$
$ka_1 = 1$
$ka_2 = b$
$a_0 = |a_1 - a_2|$ , so $ka_0 = k|a_1 - a_2| = |ka_1 - ka_2| = |1-b|$ .
Then $x=|1-b|$ . So $x=1-b$ or $x=b-1$ . The former is impossible since it would imply that $b=1-x$ , which would make $b$ negative.
So $x=b-1$ , and $b=x+1$ . $b>x$ . So $a_2 = b/k > x/k = a_0$ . This contradicts the assumption that $a_0$ is the largest element of $\{a_n\}$ .

We will now suppose, for the sake of contradiction, that $a_{i+1}$ , for $i \ge 0$ , is the largest element of $\{a_n\}$ .
Let $a_0 = 1/k$ , and let $a_1 = x/k$ . Then $k>0$ and $x>1$ .
$ka_i = 1$
$ka_{i+1} = x$
$ka_{i+2} = x-1$ (It can't be $1-x$ , since this is negative.)
$ka_{i+3} = b$
$ka_{i+1} = k|a_{i+2} - a_{i+3}| = |ka_{i+2} - ka_{i+3}| = |x-1-b|$
$x=|x-1-b|$
The option $x=x-1-b$ is impossible, since it implies $b=-1$ .
Then $x=b+1-x$ , and $2x=b+1$ , and $b=2x-1$ .
Suppose $2x-1<x$ . Then $x-1<0$ , so $x<1$ . Contradiction.
So $a_{i+3} = b/k > x/k = a_{i+1}$ . This contradicts our assumption that $a_{i+1}$ is the largest of $\{a_n\}$ .

We conclude that $\{a_n\}$ does not have a largest element, and it is therefore not bounded.

QED.

Z K Y

The post below has been deleted. Click to close.

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

darktreb

732 posts

darktreb

#11 h Dec 12, 2005, 4:39 AM • 4 Y

Y by Adventure10, jhu08, ImSh95, Mango247

This was also the first problem of the first MOP test for the Black group (USAMO winners) in 2005.

Z K Y

The post below has been deleted. Click to close.

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

Valentin Vornicu

7301 posts

Valentin Vornicu

#12 h Dec 12, 2005, 8:07 AM • 4 Y

Y by Adventure10, jhu08, ImSh95, Mango247

darktreb wrote:

This was also the first problem of the first MOP test for the Black group (USAMO winners) in 2005.

Also in the Romanian TST in 2005

Spread problem

Z K Y

The post below has been deleted. Click to close.

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

nipolo

7 posts

nipolo

#13 h Jan 27, 2006, 7:44 PM • 4 Y

Y by Adventure10, jhu08, ImSh95, Mango247

What a easy problem????

There is no bounded.It is unlimited or it has at least 2 limits

Z K Y

The post below has been deleted. Click to close.

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

ZetaX

7579 posts

ZetaX

#14 h Jan 27, 2006, 8:18 PM • 4 Y

Y by Adventure10, jhu08, ImSh95, Assassino9931

Philip_Leszczynski wrote:

[...]
We conclude that $\{a_n\}$ does not have a largest element, and it is therefore not bounded.

QED.

You can't make that assumption, e.g the sequence $a_i = 1- \frac{1}{i}$ doesn't have a largest element and is bounded.

Z K Y

The post below has been deleted. Click to close.

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

me@home

2349 posts

me@home

#15 h Mar 31, 2006, 6:47 AM • 4 Y

Y by Adventure10, jhu08, ImSh95, Mango247

I'm guessing nipolo's brief "proof" is incorrect? Or if it is correct, can someone elaborate?

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5533 posts

megarnie

#55 h Jan 30, 2023, 2:43 PM • 1 Y

Y by ImSh95

The answer is no.

Suppose $(a_i)$ was bounded.

First we get that $a_i\ge 0$ for all $i$ .

Claim: $a_n \ge 0$ for all $n$ .
Proof: Suppose some $n$ satisfied $a_n = 0$ . Note $n\ge 2$ . Then $a_{n+1} = a_{n-1}, a_{n-1} = a_{n-2}$ , which gives that $a_{n-3} = 0$ . Repeating this process we find that $a_0 = 0, a_1= 0$ , or $a_2 = 0$ , which implies $a_2 = 0$ . But then $a_0 = a_1$ , contradiction. $\square$

Claim: $a_{n+3}\ge a_n$ for all $n$ .
Proof: Note that $a_{n+2}\in \{a_{n+1} - a_n, a_{n+1} + a_n\}$ and $a_{n+3}\in \{a_{n+2} - a_{n+1}, a_{n+2} + a_{n+1}\}$ by the problem condition.
If $a_{n+2} = a_{n+1} + a_n$ , then $a_{n+3} \in \{a_n, 2a_{n+1} + a_n\}$ , which implies $a_{n+3} \ge a_n$ .

If $a_{n+2} = a_{n+1} - a_n$ , then $a_{n+3}\in \{-a_n, 2a_{n+1} - a_n\}$ . Since $a_{n+3}\ge 0$ , $a_{n+3} = 2a_{n+1} - a_n$ . Since $a_{n+1}\ge a_n$ , $a_{n+3}\ge 2a_n - a_n = a_n$ , as desired. $\square$

Now, the three sequences $(a_{3i}), (a_{3i+1}), (a_{3i+2})$ are each increasing. Since $(a_i)$ is bounded they are all eventually constant, so $a_n = a_{n+3}$ for all $n\ge C$ for some constant $C$ .

Let $a_C = x, a_{C+1} = y$ . Note that $a_{C+2} \in \{y-x, y+x\}$ and $y = |a_{C+3} - a_{C+2}| = |x - a_{C+2}|$ .

If $a_{C+2} = y-x$ , then $|2x-y| = y$ . Since $x>0$ , we have $x=y$ . This is absurd because it implies $a_{C-1} = 0$ , contradiction.
Thus, $a_{C+2} = y+x$ . Now we have $y+ x = a_{C+2} = |a_{C+3} - a_{C+4}| = |x-y|$ , which implies either $x=0$ or $y=0$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1664 posts

awesomeming327.

#56 h Feb 17, 2023, 9:25 PM • 1 Y

Y by ImSh95

Clearly, $a_n$ is nonnegative for all $n$ and $a_{n+2}=a_{n+1}-a{n}$ or $a_{n+1}+a_n$ . Let $n$ be the smallest index such that $a_n=a_{n+1}$ . Then, $a_{n-1}=0.$ However, that implies $a_{n-2}=a_{n-3}$ , contradiction. Therefore, consecutive terms are different.

Suppose that the sequence is bounded, then let $m$ be the maximum value and $M$ be the index such that $a_M=m$ . Note that $a_{M-1}$ , $a_{M+1} < m$ . $a_{M+1}$ can't be $a_M+a_{M-1}$ so it has to be $a_M-a_{M-1}$ . Now, $a_{M+1} < a_M$ so $a_{M+2}$ cannot be $a_{M+1}-a_M$ so it must be $a_{M+1}+a_M=2a_M-a_{M-1}>a_M$ , contradiction. Therefore, the sequence is not bounded.

This post has been edited 1 time. Last edited by awesomeming327., Feb 17, 2023, 9:38 PM

Z K Y

The post below has been deleted. Click to close.

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

BobsonJoe

811 posts

BobsonJoe

#57 h Feb 26, 2023, 8:16 PM • 1 Y

Y by ImSh95

Note that $a_{n+2} = a_{n+1} + a_n$ or $a_{n+2} = a_{n+1} - a_n$ . If the former case is always true, then we are trivially done. Otherwise, there exists an $n$ with $a_n > a_{n+1}$ . Shift the sequence so that $a_0 > a_1$ .

Lemma 1: For all $n$ , $a_n \ge a_1$ .
Proof: We use induction, base cases $n=0, 1$ . We can check that $a_2 = a_0 + a_1 > a_1$ . For $n > 2$ , if $a_{n} = a_{n-1} + a_{n-2}$ , we are done. Otherwise,
$a_{n} = a_{n-1} - a_{n-2} = a_{n-3} + a_{n-2} - a_{n-2} = a_{n-3} \ge a_1$
Lemma 2: For all $n$ , either $a_{n+1} \ge a_n + a_1$ or $a_{n+2} \ge a_n + a_1$ .
Proof: If $a_{n+1} = a_n + a_{n-1} \ge a_n + a_1$ are we done. Otherwise
$a_{n+1} = a_n - a_{n-1} < a_n \implies a_{n+2} = a_{n+1} + a_n \ge a_n + a_1$
Hence, we can construct an infinite subsequence, each term at least $a_1$ greater than the previous, so the sequence must be unbounded.

Z K Y

The post below has been deleted. Click to close.

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

popop614

264 posts

popop614

#58 h Jun 26, 2023, 7:31 PM • 1 Y

Y by ImSh95

If someone can please make sure that this solution is right, that would be appreciated, thank you! (I'm really iffy on this solution but it might work)

The sequence must be unbounded. Observe that all terms are positive for obvious reasons.

As a start, note that $a_{n+2} = a_{n+1} \pm a_n$ for some choice of sign. Now the sequence either starts increasing, or it starts decreasing; but if it starts decreasing, then it must increase immediately after that since we can't have any negative terms. Henceforth assume $a_0 < a_1$ . Moreover assume that $a_1 > a_2$ , as otherwise we either find a term where that happens or the sequence is trivially unbounded (always addition).

Call a value $a_i$ a $difference$ if $a_i = a_{i-1} - a_{i-2}$ .
$\textbf{Claim.}$ The smallest difference is $a_1 - a_0$ .
$\textit{Proof.}$ We have our sequence starting $a_0$ , $a_1$ , $a_1 - a_0$ . We are forced to have $a_3 = 2a_1 - a_0$ . Subtracting now gets us a difference of $a_1 > a_1 - a_0$ . Adding again and subtracting after that, we obtain a difference of $a_1 - a_0$ .

Observe that if we have $a$ , $b$ , $a + b$ as the sequence, the difference will be $a$ ; i.e. after a sufficient amount of adding, the difference will be $2$ terms back. But after the second addition we just simply keep looking further at the increasing sequence $a_1 - a_0, 2a_1 - a_0, 3a_1 - 2a_0$ $\cdots$ so the next difference will always be at least $a_1-a_0$ .

Now if at any point in the sequence we have $a$ , $b$ , $b-a$ , we are forced to add the difference $b-a$ to $b$ ; if this happens finitely many times again the sequence is trivially unbounded (infinite adding wahoo) but if it happens infinitely many times, we add a difference of at least $a_1 - a_0$ each time; thus it is unbounded.

Z K Y

The post below has been deleted. Click to close.

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

cj13609517288

1865 posts

cj13609517288

#59 h Jul 24, 2023, 2:35 AM

Y by

The answer is no, the sequence is always unbounded.

Clearly each of these terms are positive, and no two consecutive terms are equal. Consider pairs of consecutive terms(the same pair appearing multiple times in the sequence counts as a different pair). If a pair is decreasing, call it a fruity pair.

If there are finitely many fruity pairs, then the sequence is eventually strictly increasing, so it is unbounded. Therefore, there are infinitely many fruity pairs. So consider what happens when you move from one fruity pair to the next. I claim that either (the second number increases) or (it stays the same and the first one increases).

Suppose that the first fruity pair is $(a,b)$ . Then the next term has to be $a+b$ , and the term after that can either be $a$ (in that case we have completed our larger fruity pair) or $a+2b$ . The next term can be $b$ (in that case we have completed our larger fruity pair) or $2a+3b$ . Eventually this is going to get to $F_{k}a+F_{k+1}b$ and $F_{k+1}a+F_{k+2}b$ , and when we finally decide to subtract the next term is $F_{k-1}a+F_{k}b$ which is obviously greater than $b$ .

Therefore our claim is true. If the second number keeps staying the same, then the first number is unbounded. If the second number doesn't keep staying the same, then the second number is unbounded. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

OronSH

1720 posts

OronSH

#60 h Jan 14, 2024, 12:40 AM • 1 Y

Y by megarnie

No it cannot be. Consider two consecutive terms $a,b$ with $a<b$ which clearly must exist. (take either $a_0,a_1$ or $a_1,a_2$ ) then either the next term is $b+a$ giving us another pair $b,b+a$ or it is $b-a$ and then the next term will be $2b-a$ giving us pair $b-a,2b-a.$ In this process the greater term of each pair increases by either $a$ or $b-a.$ Thus the increase is $\ge \min(a,b-a)=x$ which are the difference and the smaller term in our pair. However now notice that $\min(b,(b+a)-b)=\min(a,b)\ge\min(a,b-a)=x$ and $\min(b-a,(2b-a)-(b-a))=\min(b-a,b)\ge\min(a,b-a)=x$ so as long as we repeat this both the smaller term and the difference in each of these pairs will be $\ge x.$ Thus at each step the largest term increases by at least $x$ so it must be unbounded.

Z K Y

The post below has been deleted. Click to close.

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

Assassino9931

1197 posts

Assassino9931

#61 h Mar 12, 2024, 11:13 PM

Y by

blackbluecar wrote:

The sequence is unbounded...

Notice that $a_2$ and $a_3$ are certainly positive so lets say wlog that $a_0$ and $a_1$ are positive. Notice that $a_k=u \cdot a_0+v \cdot a_1$ for some positive integers $u$ and $v$ . Thus, if $b_1,b_2,...$ is an increasing subsequence of $a_1,a_2,...$ then it must be unbounded.

Why must it be unbounded? If e.g. $a_0 = 1$ and $a_1 = 2$ , so $a_k = u_k + 2v_k$ and we might have $u_{k+1} = u_k + 2A$ , $v_{k+1} = v_k - A$ . This would imply $a_{k+1} = a_k$ which is not really possible, as almost all solutions show, but the situation here is evidence that the unboundedness is not too obvious perhaps? What if the increments can be some very small linear combinations of $a_0$ and $a_1$ ?

This post has been edited 1 time. Last edited by Assassino9931, Mar 12, 2024, 11:20 PM

Z K Y

The post below has been deleted. Click to close.

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

asdf334

7579 posts

asdf334

#62 h Apr 4, 2024, 2:44 AM • 2 Y

Y by MihaiT, Assassino9931

Assume the sequence is bounded. Notice that no value is equal to zero and so all values are positive (furthermore no adjacent values are equal).

For any value $i$ let $f(i)\in \{i+1,i+2\}$ be a value such that $a_{f(i)}>a_i$ . This value exists as it is impossible to have $a_{i+1},a_{i+2}<a_i$ .

Then we can create a sequence of values $s_i$ such that
$a_{s_1}<a_{s_2}<\dots<a_{s_n}<\dots$ and also choose the smallest constant $C$ which is at least each of these values. Write $b_i=a_{s_i}$ for convenience.

Now we can analyze the relationship between three consecutive $s_n$ , $s_{n+1}$ , and $s_{n+2}$ for large $n$ .

Notice that $s_{n+2}=s_n+2$ and $s_{n+1}=s_n+1$ cannot happen; this would imply $b_{n+2}=b_{n+1}+b_n>C$ .
Notice that $s_{n+2}=s_n+4$ and $s_{n+1}=s_n+2$ cannot happen; this would imply
$(b_{n+1}-b_n)+(b_{n+2}-b_{n+1})=b_{n+1}.$
Notice that all remaining cases necessarily have $b_n$ , $b_{n+1}$ , and $b_{n+2}$ in an arithmetic sequence.

Hence we violate the boundedness condition. Done.

Z K Y

The post below has been deleted. Click to close.

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

Ywgh1

136 posts

Ywgh1

#63 h Aug 9, 2024, 12:10 PM

Y by

First of all, it's clear that $a_n$ is nonnegative for all $n$
and that $a_{n+2}= a_{n+1}-a_{n}$ or $a_{n+2}= a_{n+1}+a_{n}$

Claim : All consecutive terms are different.

Assume FTSOC that $a_n=a_{n+1}$ are the first two consecutive terms.
Then this means $a_{n-1}=0$ implying that $a_{n-2}=a_{n-3}$ . A contradiction.

Now let $N$ be a positive integer such that $a_N$ is the maximum term in the sequence. This means that $a_{N+1} \neq a_{N}+a_{N-1}$ as $a_N > a_{N+1}, a_{N-1}$ .
So $a_{N+1}= a_{N}-a_{N-1}$ , but this forces $a_{N+2}$ to be more than $a_N$ , contradiction. Implying that the sequence is unbounded.

This post has been edited 3 times. Last edited by Ywgh1, Aug 9, 2024, 12:18 PM

Z K Y

The post below has been deleted. Click to close.

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

Mathandski

711 posts

Mathandski

#65 h Sep 6, 2024, 11:24 PM

Y by

Subjective Rating (MOHs) $\text{[math]}$

Attachments:

This post has been edited 1 time. Last edited by Mathandski, Sep 6, 2024, 11:24 PM

Z K Y

The post below has been deleted. Click to close.

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

blueprimes

303 posts

blueprimes

#66 h Sep 7, 2024, 12:10 AM

Y by

This problem I would say lies in a gray area between 5-10 MOHS as it is very easy to fakesolve (i.e, proving a subsequence is increasing but not showing divergence, assuming a maximum term.) Anyways, here is a solution that hasn't been posted yet I believe.

The answer is no, the sequence cannot be bounded. FTSOC, assume it can. Clearly $a_n = a_{n - 1} \pm a_{n - 2}$ for all $n \ge 2$ so define:

n is additive if $a_n = a_{n - 1} + a_{n - 2}$
n is subtractive if $a_n = a_{n - 1} - a_{n - 2}$

It is easy to show that all terms must be positive. Moreover, we must have an infinite number of subtractive integers as otherwise, the sequence eventually assumes a Fibonacci recurrence which diverges.

Lemma 1: For every additive $n$ , the smallest $g > n$ that is subtractive satisfies $a_g \ge a_{n - 2}$ .
Proof. Since $a_{n - 2}, a_{n - 1}, \dots, a_{g - 3}$ has a Fibonacci recurrence it is increasing, then
$a_g = a_{g - 1} - a_{g - 2} = (a_{g - 2} + a_{g - 3}) - a_{g - 2}\ = a_{g - 3} \ge a_{n - 2}.$
Claim 1: For every subtractive $p$ , there exists a larger subtractive $q$ where $2a_p < a_q$ .
Proof. Let $s$ be the minimal subtractive integer after $p$ , we consider cases on what $s$ is. For brevity let $a_{p - 2} = x, a_{p - 1} = y$ , it is easy to check the case $s = p + 1$ fails.

Case 1: $s = p + 2$ .
The sequence necessarily has
$a_{p - 2}, a_{p - 1}, a_p, a_{p + 1}, a_{p + 2}, a_{p + 3} = x, y, y - x, 2y - x, y, 3y - x$ and applying Lemma 1 and letting $n = p + 3$ and $q = g$ yields $a_q \ge 2y - x > 2(y - x) = 2a_p$ as wanted.

Case 2: $s = p + 3$ .
We use a similar approach, the sequence has
$a_{p - 2}, a_{p - 1}, a_p, a_{p + 1}, a_{p + 2}, a_{p + 3}, a_{p + 4} = x, y, y - x, 2y - x, 3y - 2x, y - x, 4y - 3x$ and applying Lemma 1 again with $n = p + 4, q = g$ yields $a_q \ge 3y - 2x > 2(y - x) = 2a_p$ which works.

Case 3: $s \ge p + 4$ .
So
$a_{p - 2}, a_{p - 1}, a_p, a_{p + 1}, a_{p + 2}, a_{p + 3}, a_{p + 4} = x, y, y - x, 2y - x, 3y - 2x, 5y - 3x, \dots$ now Lemma 1 where $n = p + 4, q = g$ gives $a_q \ge 2y - x > 2(y - x) = 2a_p$ .

The claim is proven, now recurring it we can extract a subsequence of the original sequence where every proceeding term is more than twice the previous which must diverge. We are done.

This post has been edited 5 times. Last edited by blueprimes, Sep 7, 2024, 5:36 PM

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1246 posts

ezpotd

#67 h Oct 25, 2024, 12:14 PM

Y by

Assume that the sequence is bounded, this then forces a maximum. We then show some other number in the sequence is bigger than the maximum.

Claim: No two consecutive numbers in the sequence are equal.
Proof: Assume there exists a smallest $i$ with $a_{i} = a_{i + 1}$ . This then forces $a_{i - 1} = 0, a_{i - 2} = a_i, a_{i -3} = a_{i - 2}$ , so if $i > 3$ we get a contradiction. Otherwise, if $i = 3$ this forces $a_2 = 0$ , contradiction, if $i = 2$ this forces $a_1 = 0$ , contradiction, if $i = 1$ this violates the problem conditions.

Now take the maximum $m = a_j$ , then take $a_{j + 1}$ . If it is greater than $m$ we are done, if it is equal to done it violates the claim, contradiction, if it is less than $m$ it forces $a_{j + 2} = m + a_{j + 1}$ , done ( $a_{j + 2} > m$ since $a_{j + 1} \neq 0$ since $a_{j + 2} = a_{j+ 3}$ by the claim), done.

Z K Y

The post below has been deleted. Click to close.

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

dgrozev

2459 posts

dgrozev

#68 h Oct 26, 2024, 12:29 PM

Y by

ezpotd wrote:

Assume that the sequence is bounded, this then forces a maximum. We then show some other number in the sequence is bigger than the maximum.
---
Now take the maximum $m = a_j$ , then take $a_{j + 1}$ . If it is greater than $m$ we are done, if it is equal to done it violates the claim, contradiction, if it is less than $m$ it forces $a_{j + 2} = m + a_{j + 1}$ , done ( $a_{j + 2} > m$ since $a_{j + 1} \neq 0$ since $a_{j + 2} = a_{j+ 3}$ by the claim), done.

There is an issue. The sequence may not have a maximum term (it's infinite). So, it's not so trivial. But, it can be modified as in #46, and you can take $\limsup a_n$ and get a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1246 posts

ezpotd

#69 h Oct 28, 2024, 12:02 AM

Y by

oops. quick and easy fix:
Assume the sequence is bounded, then the sequence does have a limit supremum $A$ . Call a number good if it is at least $0.99A$ . Some good number must exist, otherwise the limit supremum would be less than $0.99A$ . We force a contradiction

Consider a good number $a_i$ that is followed by a smaller number $a_{i + 1}$ . Then we must have $a_{i + 2} = a_{i + 1} + a_{i}$ . If $a_{i + 3} = a_{i + 2} - a_{i + 1} = a_{i}$ , we have two consecutive good numbers that are decreasing, this forces $a_{i + 4} = a_{i + 3} + a_{i + 2} > A$ . If $a_{i + 3} = a_{i + 2} + a_{i + 1}$ , either this is greater than $A$ and we are done or we have $a_{i + 3} > a_{i + 2}$ . If $a_{i + 4} = a_{i + 3} + a_{i + 2}$ the sum is greater than $A$ and we are instantly done, if $a_{i + 4} = a_{i + 3} -a_{i + 2} = a_{i + 1}$ , we have then proved that $a_{i + 3} = a_{i} + 2a_{i + 1}$ , so $a_{i + 3n} = a_{i} + 2n$ , obviously contradiction since it would imply $a$ unbounded.

If no good number is ever followed by a smaller number, at some point all the remaining numbers in the sequence are good, implying that the difference between them is at most $0.01A$ , which obviously fails.

i just realized how horrible this writeup is but im too lazy.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

790 posts

shendrew7

#70 h Yesterday at 2:34 AM

Y by

$\boxed{\text{No.}}$ Our solution follows from three observations:

All terms must positive and nonzero, with no two consecutive terms equal.
Every term is a linear combination of $a_1$ , $a_2$ , so terms must differ by a multiple of $a_1-a_2$ .
We always have $a_n < a_{n+1}$ or $a_n < a_{n+2}$ , so the max increases by $\ge |a_1-a_2|$ every two terms, which finishes. $\blacksquare$

Z K Y