"pseudo-Fibonnaci" sequence

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

"pseudo-Fibonnaci" sequence

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2006, Algebra 3

The post below has been deleted. Click to close.

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

1145 posts

#1 h Jun 28, 2007, 5:45 PM • 2 Y

Y by Adventure10, Mango247

The sequence $c_{0}, c_{1}, . . . , c_{n}, . . .$ is defined by $c_{0}= 1, c_{1}= 0$ , and $c_{n+2}= c_{n+1}+c_{n}$ for $n \geq 0$ . Consider the set $S$ of ordered pairs $(x, y)$ for which there is a finite set $J$ of positive integers such that $x=\textstyle\sum_{j \in J}{c_{j}}$ , $y=\textstyle\sum_{j \in J}{c_{j-1}}$ . Prove that there exist real numbers $\alpha$ , $\beta$ , and $M$ with the following property: An ordered pair of nonnegative integers $(x, y)$ satisfies the inequality $m < \alpha x+\beta y < M$ if and only if $(x, y) \in S$ .

Remark: A sum over the elements of the empty set is assumed to be $0$ .

This post has been edited 1 time. Last edited by djmathman, Jun 27, 2015, 12:06 AM
Reason: slight formatting changes

Z K Y

The post below has been deleted. Click to close.

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

357 posts

#2 h Jul 21, 2007, 9:58 AM • 2 Y

Y by Adventure10, Mango247

Anyone has a solution for this problem ? I can find the solution for all algebra problems in the shortlist except this problem..

Z K Y

The post below has been deleted. Click to close.

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

773 posts

#3 h Jul 21, 2007, 11:32 AM • 2 Y

Y by Adventure10, Mango247

I think that I didn't understand the problem,
you want we showing that S is limited?
I think that if we take $(x_{n},y_{n})=(\sum_{i=1}^{n}c_{i},\sum_{i=1}^{n}c_{i-1})$
$\exists n\in\mathbb{N}: \ min(x_{n},y_{n})=min(\sum_{i=1}^{n}c_{i},\sum_{i=1}^{n}c_{i-1})>M$
then we have $(x_{n},y_{n})\in S$ and $\alpha x_{n}+\beta y_{n}>M$

Z K Y

The post below has been deleted. Click to close.

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

161 posts

#4 h Jul 24, 2007, 6:07 AM • 2 Y

Y by Adventure10, Mango247

I'm sorry aviateurpilot, I don't really understand your post. I worked on this problem a couple weeks ago for a couple days and couldn't hammer together a full proof. I have good reason to believe that $(x,y)\in S$ if and only if $-\gamma-1<x-\gamma y<\gamma$ where $\gamma$ is the positive real such that $\gamma^{2}=\gamma+1$ , but the proof always eludes me. I'll give it another try, but if anyone can solve this I would love to see it too.

Z K Y

The post below has been deleted. Click to close.

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

161 posts

#5 h Jul 25, 2007, 7:54 PM • 2 Y

Y by Adventure10, Mango247

Okay, I think that I have obtained a solution. If anyone sees errors in this, let me know so I can try to fix them, and also I would love to see a shorter way to do this problem if there is one.

I claim that $(x,y)\in S$ if and only if $-1-\gamma<x-\gamma y<\gamma$ where $\gamma$ is the positive root of $x^{2}-x-1$ .

First, we need an important fact about Fibonacci numbers. Let $f_{0}=0,f_{1}=1$ and $f_{n+2}=f_{n+1}+f_{n}$ for all $n\ge 0$ . Then we have for all $k\ge 0$

$f_{k+1}-\gamma f_{k}=\frac{1}{2\gamma-1}(\gamma^{k+1}-(1-\gamma)^{k+1})-\frac{\gamma}{2\gamma-1}(\gamma^{k}-(1-\gamma)^{k})$
$=\frac{1}{2\gamma-1}(\gamma (1-\gamma)^{k}-(1-\gamma)^{k+1})=(1-\gamma)^{k}$ .

Knowing this, we can now proceed. First suppose $(x,y)\in S$ . Then we have some set $J$ as mentioned in the problem, and so

$x-\gamma y=\sum_{j\in J}(c_{j}-\gamma c_{j-1})=\sum_{j\in J}(1-\gamma)^{j-1}$ for the moment as long as we ignore the fact if $1\in J$ . If we let $p$ be the greatest odd element in $J$ , we can deduce that
$x-\gamma y\le (1-\gamma)^{0}+(1-\gamma)^{2}+\cdots+(1-\gamma)^{p-1}<\frac{1}{1-(1-\gamma)^{2}}=\gamma$ .

Similiarly, if we account that $1$ can be in $J$ , we have $x-\gamma y>(0-\gamma)+(1-\gamma)+(1-\gamma)^{3}+\cdots>-\gamma+\frac{1-\gamma}{1-(1-\gamma)^{2}}=-1-\gamma$ . This concludes the first direction.

To prove the other direction, suppose the two integers $x,y$ satisfy $-1-\gamma<x-\gamma y<\gamma$ . Now, for any positive integer $x$ , consider the following algorithm: Pick the greatest Fibonacci number less than or equal to $x$ , subtract it, and then repeat until we arrive at zero. In this way, we can derive a set $J$ such that $\sum_{j\in J}c_{j}=x$ and we can guarantee that $1$ or $2$ is not in $J$ (this means that there is at most one $1$ in the sum).

Now, for any $i\ge 4$ , if $i-2$ and $i-1$ do not belong to $J$ and $i$ does, we can remove $i$ from the set and add $i-2$ and $i-1$ to the set. In this manner, we start with the smallest value in $J$ and try to achieve a configuration with precisely one $1$ if we do not have it already. Suppose that there is precisely one $1$ in some partition of $x$ , i.e., $min{J}=3$ . Then for the corresponding $y$ induced from this $J$ , we have $x-\gamma y=\sum_{j\in J}c_{j}-\gamma c_{j-1}$ from which we can deduce the two bounds:

$x-\gamma y\le (1-\gamma)+(1-\gamma)^{2}+(1-\gamma)^{4}+\cdots<0$ and

$x-\gamma y\ge (1-\gamma)+(1-\gamma)^{3}+\cdots>-1$ .

By moving adding $1$ to $J$ , we can increase $y$ by 1 without changing $x$ , and so $-\gamma-1<x-\gamma y<-\gamma$ , thus giving us a new value in the interval. Also, before adding $1$ to $J$ , if we just remove $3$ and add $2$ , we do not change $x$ but we decrease $y$ by 1. Thus $\gamma-1<x-\gamma y<\gamma$ which also gives us a new value. But since the interval is of length $2\gamma+1$ , there can only be at most $3$ values in this interval. But since they are all accounted for, we can finish this case.

So all we have left is the case when any partition of $x$ does not contain exactly one $1$ . In this case, with the same strategy above we can find that $x-\gamma y<\gamma-1$ . However, to derive a lower bound, we must notice that the only way for $x$ to not contain exactly one $1$ is if the smallest element in $J$ is even (because of the type of "move" described above). Hence for some $t\in\mathbb{N}$ we have $x-\gamma y>(1-\gamma)^{2t}+(1-\gamma)^{2t+1}+(1-\gamma)^{2t+3}+\cdots>0$ . But then using this bound, we know that there cannot be a pair $(x,y)$ in the region with a value greater than this one, and moreover, only one value with a different $y$ can fit below this interval. But to derive this value, simply just add $1$ to the set $J$ , and from here we obtain the desired $y$ . Because there are no more possibilites for $y$ , we are finished.

Z K Y

The post below has been deleted. Click to close.

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

30 posts

#6 h Sep 28, 2018, 4:50 PM • 2 Y

Y by Adventure10, Mango247

O strongly believe this problem(and therefore zgorkster's solution) is incorrect. The IF part is pretty intuitive once one notices the fact that $c_{n}=F_{n-1}$ and achieves the bound
$-\alpha -1<x-\alpha *y<\alpha$ . But then you realoze that for every $y$ we have at least two integers $x$ satisfying the above inequality, but Zeckendorf's representation tells us that for every y only one x is possible

Z K Y

The post below has been deleted. Click to close.

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

30 posts

#7 h Sep 28, 2018, 5:03 PM • 1 Y

Y by Adventure10

Altough there's one correction that would make the problem correct: if instead he asked that the statement is true for all pairs $(x,y)$ of POSITIVE INTEGERS, because then the lower bound would be simply $-1<x-y\alpha<\alpha\iff y\in (\frac{x}{\alpha}-1,\frac{x}{\alpha}+\frac{1}{\alpha}$ . But then it wouldn't make sense to redefine the sequence $c_{n}$ by shifitng Fibonacci's indices if you weren't gonna use $c_{0}=F_{-1}=1$
What a mess

This post has been edited 1 time. Last edited by Samusasuke, Sep 28, 2018, 5:03 PM

Z K Y

The post below has been deleted. Click to close.

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

327 posts

#8 h Jun 4, 2020, 3:03 PM

Y by

First let $\phi_1>\phi_2$ be the roots to $\phi^2-\phi-1=0$ . That is, $\phi_1=\frac{1+\sqrt{5}}{2}$ and $\phi_2=\frac{1-\sqrt{5}}{2}$ .
We claim that $m=-1$ , $M=\phi_1$ , $\alpha=\phi_2$ and $\beta=1$ works.

It is well-known that for all $n\geq 0$ , $c_n=\frac{\phi_1^{n-1}-\phi_2^{n-1}}{\sqrt{5}}$ Hence,
$c_n\phi_2+c_{n-1}=\phi_2\left(\frac{\phi_1^{n-1}-\phi_2^{n-1}}{\sqrt{5}}\right)+\frac{\phi_1^{n-2}-\phi_2^{n-2}}{\sqrt{5}}=\phi_2^{n-1}$
Let the pairs in $S$ be $(a_J, b_J)$ with $J\in\mathbb{N}$ , with $a_J=\sum_{j\in J} c_j$ and $b_J=\sum_{j\in J} c_{j-1}$ .

We first show that $\phi_2 a_J+b_J\in (-1,\phi_1)$ .
$\phi_2 a_J+b_J=\sum_{j\in J} (c_j \phi_2+c_{j-1})=\sum_{j\in J} \phi_2^{j-1}$ Since $-1<\phi<0$ , this sum is bounded by the following estimate:
$\sum_{k=0}^{\infty} \phi_2^{2k+1}<\sum_{j\in J} \phi_2^{j-1}<\sum_{k=0}^{\infty} \phi_2^{2k}$ Note that $\sum_{k=0}^{\infty} \phi_2^{2k+1}=\frac{\phi_2}{1-\phi_2^2}=-1$ and $\sum_{k=0}^{\infty} \phi_2^{2k}=\frac{1}{1-\phi_2^2}=-\frac{1}{\phi_2}=\phi_1$
Hence for all $(x,y)\in S$ , we have $\alpha x+\beta y\in (m,M)$ .

Next we show the other direction.
Claim: For all $(x,y)\in \mathbb{N}^2$ with $-1<\phi_2 x+y<\phi_2$ , there exists $J\subset\mathbb{N}$ such that $\phi_2 x+y=\sum_{j\in J} \phi_2^{j-1}$ .
Proof: For $x=y=0$ , choose $J=\emptyset$ . Suppose at least one of $x$ and $y$ is nonzero. Then
$\phi_2 x+y=\phi_2^{i_1}+\phi_2^{i_2}+\cdots+\phi_2^{i_k}$ for some sequence $i_1\leq i_2\leq \cdots \leq i_k$ . This sequence exists, as we can choose $i_1=i_2=\cdots=i_y=0$ , and $i_{y+1}=i_{y+2}=\cdots=i_{y+x}=1$ .

From all such sequences, consider those with minimum length $k$ . From these, consider those with minimum $i_1$ . Then consider those with minimum $i_2$ , then minimum $i_3$ , and so on. We end up with a sequence $j_1\leq j_2\leq \cdots \leq j_k$ . It suffices to show that all these terms are different.
Suppose otherwise, i.e. there exists $r$ such that $j_r=j_{r+1}$ .

Case I: $j_r=j_{r+1}\geq 2$ .
Then noting that $2\phi_2^2=1+\phi_2+\phi_2^3-\phi_2=1+\phi_2^3$ , we can replace $(j_r,j_{r+1})$ with $(j_r-2,j_r+1)$ . This contradicts the minimality of elements in the sequence.

Case II: $j_r=j_{r+1}=0$ .
Note that $j_t\neq 1$ for all $t$ , as $1+\phi_2=\phi_2^2$ and we can replace the $(0,1)$ with $2$ . This contradicts the minimality of sequence length.
In fact, we cannot have two elements in the sequence differing by $1$ . Hence,
$\phi_2 x+y=\sum_{r=1}^k \phi_2 j_r>2+\phi_2^3+\phi_2^5+\cdots=2-\phi_2^2=\phi_1$ Contradiction.

Case III: $j_r=j_{r+1}=1$ .
Note that $j_t\neq 0$ or $2$ for all $t$ . Following the same logic as Case II, we cannot have two elements in the sequence differing by $1$ .
$\phi_2 x+y<2\phi_2+\phi_2^4+\phi_2^6+\cdots=2\phi_2-\phi_2^3=1$ Contradiction.

Hence the lemma is proven. Now note that for all pairs of $(x,y)$ with $-1<\phi_2x+y<\phi_1$ , there exists $J_{x,y}\subset \mathbb{N}$ such that $\sum_{j\in J_{x,y}}\phi_2^{j-1}=\phi_2 x+y$ . Then $\phi_2 x+y=\phi_2 a_{J_{x,y}}+b_{J_{x,y}}$ . Since $\phi_2$ is irrational, it follows that $a_{J_{x,y}}=x$ and $b_{J_{x,y}}=y$ . Hence we are done.

Z K Y

The post below has been deleted. Click to close.

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

186 posts

#9 h Dec 2, 2020, 6:26 AM • 1 Y

Y by anser

Solved with anser.

Let $\phi = \frac{1+\sqrt{5}}{2}$ , satisfying $\phi^2 - \phi - 1 = 0$ .

We'll show $-\phi^2 < x - \phi y < \phi$ for all $(x, y) \in S$ . First by solving the recurrence we get $c_n = -\frac{1 - \sqrt{5}}{2\sqrt{5}}\cdot \phi^n + \frac{1 + \sqrt{5}}{2\sqrt{5}}\cdot \left(-\frac{1}{\phi}\right)^n$ . Then we have $c_{n + 1} - \phi c_n = -\phi \cdot \left(-\frac{1}{\phi}\right)^n.$ If $(x, y) \in S$ , then $x - y$ is the sum of this over distinct values of $n \geq 0$ . This means $x - \phi y$ is between $-\phi\cdot \left(1 + \frac{1}{\phi^2} + \cdots\right) = -\phi \cdot \frac{\phi^2}{\phi^2 - 1} = -\phi^2$ when the sum has only positive terms, and $-\phi \cdot -\frac{1}{\phi}\cdot \left(1 + \frac{1}{\phi^2} + \cdots\right) = \phi$ when the sum has only negative terms.

Now suppose that $-\phi^2 < x-\phi y < \phi$ , or $\frac{x}{\phi} - 1 < y < \frac{x}{\phi} + \phi$ . Let the Fibonacci representation of $x$ be the unique way to express $x$ as a sum of nonadjacent Fibonacci numbers. The claim is that the smallest term in the Fibonacci representation of $x$ is $F_n$ for $n$ even iff $(\frac{x}{\phi} - 1, \frac{x}{\phi} + \phi)$ contains 3 integers, that is, $2-\phi < \left\{\frac{x}{\phi}\right\} < 1$ .

Since $F_n = \frac{1}{\sqrt{5}}\phi^n - \frac{1}{\sqrt{5}}\frac{1}{(-\phi)^n}$ ,
$\frac{F_n}{\phi} = \frac{1}{\sqrt{5}}\phi^{n-1} + \frac{1}{\sqrt{5}}\frac{1}{(-\phi)^{n+1}} = f_{n-1} + \frac{1}{\sqrt{5}}\left(\frac{1}{(-\phi)^{n-1}} + \frac{1}{(-\phi)^{n+1}}\right).$ So $\left\{\frac{x}{\phi}\right\} = \sum_i \frac{1}{\sqrt{5}}\left(\frac{1}{(-\phi)^{i-1}} + \frac{1}{(-\phi)^{i+1}}\right)$ , where the sum is over all $i$ s.t. $F_i$ is in the Fibonacci representation of $x$ .

The maximum and minimum possible values (both unattainable) of this sum in some order are given by
$\frac{1}{\sqrt{5}}\left[\frac{1}{(-\phi)^{n-1}} + 2\left(\frac{1}{(-\phi)^{n+1}} + \frac{1}{(-\phi)^{n+3}} + \cdots\right)\right]= \frac{1}{\sqrt{5}}\cdot\frac{1}{(-\phi)^{n-1}}(3\phi - 4)$ and
$\frac{1}{\sqrt{5}}\left[\frac{1}{(-\phi)^{n-1}} + \frac{1}{(-\phi)^{n+1}} + \frac{1}{(-\phi)^{n+2}} + 2\left( \frac{1}{(-\phi)^{n+4}} + \cdots\right)\right] = \frac{1}{\sqrt{5}}\cdot\frac{1}{(-\phi)^{n-1}}(2\phi -1).$
When $n$ is even, $\frac{1}{\sqrt{5}}\cdot\frac{1}{(-\phi)^{n-1}}(3\phi - 4) < 0$ , and $\frac{1}{\sqrt{5}}\cdot\frac{1}{(-\phi)^{n-1}}(2\phi -1)\ge \frac{1}{\sqrt{5}}\cdot\frac{1}{-\phi}(2\phi - 1) = -\phi + 1$ , so $2-\phi < \{\frac{x}{\phi}\} < 1$ .

When $n$ is odd (note $n\ge 3$ ), then $\frac{1}{\sqrt{5}}\cdot\frac{1}{(-\phi)^{n-1}}(3\phi - 4) > 0$ , and $\frac{1}{\sqrt{5}}\cdot \frac{1}{(-\phi)^{n-1}}(2\phi -1) \leq \frac{1}{\sqrt{5}\cdot \phi^2}\cdot (2\phi - 1) = 2 - \phi$ , so the $0 < \{\frac{x}{\phi}\} < 2-\phi$ .

We can always obtain 2 possibilities for $y$ , depending on whether or not we include $c_1 = 0$ in the sum for $x$ . If the smallest term in the Fibonacci representation of $x$ is $F_n$ for $n$ even, then by "breaking down" $F_n$ , we may express $x$ as a sum of 1 and some larger Fibonacci numbers. Then there are 3 possibilities for $y$ by considering whether we choose the 1 in $x$ to be $c_3$ , $c_2$ , or $c_3 + c_1$ .

Z K Y

The post below has been deleted. Click to close.

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

1446 posts

#10 h Feb 26, 2022, 1:23 AM

Y by

For typesetting purposes let $a = \phi = \frac{\sqrt{5}+1}{2}$ . We claim that a pair of nonnegative integers $(x,y)$ is in $S$ iff $-1-a < x-ay < a.$
First, we prove that this is necessary. Note that for positive $n$ , $c_{n+1}$ is the $n$ th Fibbonaci number and is therefore equal to $\frac{a^n - (-a)^{-n}}{\sqrt{5}}$ . Therefore, for $n>2$ , $c_n-ac_{n-1}$ can be expressed as $\frac{1}{\sqrt{5}} ((a^{n-1} - (-a)^{-(n-1)})-a(a^{n-2} - (-a)^{-(n-2)}) = \frac{1}{\sqrt{5}}(a(-a)^{-(n-2)}-(-a)^{-(n-1)}).$
To get a lower bound for $x-ay$ , take all positive integers $j$ where $c_j-ac_{j-1}$ is negative, and add the $c_j-ac_{j-1}$ value for each $j$ . Notice that for $j\ge 2$ this quantity is only negative when $j$ is odd, and when $j=1$ the quantity is negative, so these are the terms that we need to add up. Note that when $j\ge 2$ and $j$ is odd we have $c_j-ac_{j-1} = \frac{1}{\sqrt{5}}(-a^{-j+3}-a^{-j+1}).$ As this is a geometric sequence, it's sum is $\frac{1}{\sqrt{5}}(-1-a^{-2})\cdot \frac{1}{1-a^{-2}} = -1$ after some computation. Considering $j=1$ , we add another $0-a\cdot 1 = -a$ , making a lower bound for $x-ay$ equal to $-1-a$ .

Similarly, to get an upper bound for $x-ay$ , take all positive integers $j$ where $c_j-ac_{j-1}$ is negative, and add the $c_j-ac_{j-1}$ value for each $j$ . Notice that for $j\ge 2$ this quantity is only positive when $j$ is even, and we don't have to account for $j=1$ . Note that when $j$ is even we have $c_j-ac_{j-1} = \frac{1}{\sqrt{5}}(a^{-j+3}+a^{-j+1}).$ As this is a geometric sequence, it's sum is $\frac{1}{\sqrt{5}}(a+a^{-1})\cdot \frac{1}{1-a^{-2}} = a$ using an earlier computation. Thus an upper bound for $x-ay$ is $a$ . This proves necessity.

Now we prove sufficiency. If we take a particular set of $c_i$ that sum to $x$ , this gives us a corresponding $y$ that works. Note that for a particular $x$ there are either two or three values of $y$ that could work. Let $Z$ be the Zeckendorf representation of $x$ ( $x$ written as a sum of nonconsecutive Fibonacci numbers). If there are two possible values of $y$ , then noting that we can take the $c_i$ corresponding to $Z$ , or take the $c_i$ corresponding to $z$ in addition to $c_1$ gives us two values of $y$ that work. The $x$ that have three possible values of $y$ that could work can be solved by the following claim:

Claim: If $x$ has three possible values of $y$ , then the smallest element of $Z$ is equal to $F_k$ , where $k$ is even. ( $F_0 = 0, F_1 =1$ )
Proof. It suffices to prove the contrapositive: when the lowest element of $Z$ is equal to $F_k$ for an odd $k>1$ , there are only two possible values of $y$ appearing from that $x$ . Define two numbers to be equivalent modulo $a$ if they differ by a multiple of $a$ . Then it is easy to show that we need to prove $x$ is equivalent to a number between $0$ and $a-1$ modulo $a$ (exclusive).

For every Fibonacci number $F_i$ in $Z$ , consider adjusting to $F_i - aF_{i-1}$ . It is not hard to show the adjustment is negative if $i$ is even and positive if $i$ is odd. The sum of all these adjusted terms must clearly be equivalent to $x$ modulo $a$ . The adjusted term for $F_k$ must be equal to $\frac{1}{\sqrt{5}}(a^{-k+2}+a^{-k})$ by earlier work. Now we place upper and lower bounds to the sum of the remaining adjusted terms.

An lower bound can be formed by taking all possible adjusted terms coming from even $F_i$ . Because this is the Zeckendorf representation $F_{k+1}$ cannot be included, thus the minimum possible value is $\frac{1}{\sqrt{5}}(-a^{-j+2}-a^{-j})$ summed over all even values of $j$ at least $k+3$ , which is equal to $\frac{1}{\sqrt{5}}(-a^{-k-1}-a^{-k-3})\cdot\frac{1}{1-a^{-2}} = \frac{1}{\sqrt{5}}(-a^{-k}-a^{-k-2}).$

An upper bound can be formed by taking all possible adjusted terms coming from odd $F_i$ greater than $k$ . This is equal to $\frac{1}{\sqrt{5}}(a^{-j+2}+a^{-j})$ summed over all even $j$ at least $k+2$ , which is equal to $\frac{1}{\sqrt{5}}(a^{-k}+a^{-k-2})\cdot\frac{1}{1-a^{-2}} = \frac{1}{\sqrt{5}}(a^{-k+1}+a^{-k-1}).$

Therefore, the sum of all adjusted terms must be positive, and it must be less than $\frac{1}{\sqrt{5}}(a^{-k+2}+a^{-k+1}+a^{-k}+a^{-k-1}) \le \frac{1}{\sqrt{5}}(a^{-1}+a^{-2}+a^{-3}+a^{-4}) = a-1$ , proving the claim. $\blacksquare$

Now take the Zeckendorf representation of $x$ and replace $F_k$ by $F_{k-1} + F_{k-3} + F_3 + F_2$ . Substitute the appropriate $c_i$ (with $i>2$ ), noting that we use $c_3$ . This allows us to represent one $y$ . Now replacing $c_3$ with $c_2$ gives us a way to represent a lower $y$ , and adding $c_1$ allows us to represent a higher $y$ . Therefore, we can represent three values of $y$ , finishing the problem.

Z K Y

The post below has been deleted. Click to close.

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

266 posts

#11 h Jan 9, 2024, 4:16 PM

Y by

Set $\phi$ to be the golden ratio. Observe that
$(1 - \phi)^n = c_{n+2} - c_{n+1}\phi;$ Indeed, verify that $\frac{1}{1 - \phi} = -\phi$ since this implies $\phi^2 = \phi + 1$ , and then induction suffices.

We claim that $(x,y) \in S \iff -1 - \phi < x - \phi y < \phi$ . Indeed, defining $x$ and $y$ for a fixed set, we have
$x - y\phi = \sum_{s \in S} (1 - \phi)^{s - 1}.$ On the one hand,
$\sum_{s \in S} (1 - \phi)^{s - 1} \ge (1-\phi)^{-1} + (1 - \phi)^{-3} + \cdots = \frac{1}{(1-\phi)(1 - (1 - \phi)^2)} = \frac{1}{(1 - \phi)(\phi - 1) } = -1-\phi,$ on the other hand
$\sum_{s \in S} (1 - \phi)^{s - 1} \le (1 - \phi)^0 + (1 - \phi)^2 + \cdots = \phi.$ This proves necessity.

Suppose $\phi > x - \phi y > 0.$ Then for each positive $x$ , there is a unique $y$ which satisfies the inequality. Particularly,
$\left \lfloor \frac{x}{\phi} \right \rfloor = y.$
We will create some process which never terminates, allowing us to generate solutions.

Note that for $x=0$ , $y=0$ , we can set $x = 0$ .
Whenever we add $c_2$ , $x$ increments by $1$ , and $y$ increments by $0$ . Whenever we add $c_3$ , $x$ increments by $1$ , and $y$ increments by $1$ .

Now when $x$ increments by $1$ , $y$ will increment by at most $1$ . Note that $y$ increments at most twice in a row, and $y$ stays fixed at most once in a row.

At any given time, we take the two largest terms with adjacent indices and merge them, i.e. $c_n + c_{n+1} = c_{n+2}$ . We will show this process never generates a term with a coefficient of $2$ .

We show that $c_n$ for $n > 2$ never doubles up. Firstly, $c_3$ never doubles up, since before any $c_3$ placement we are forced to put a $c_2$ , so the first $c_3$ is absorbed by either $c_2$ or $c_4$ . If there is a leftover $c_3$ , the first $c_3$ gets turned into $c_4$ , and then $c_3$ merges with $c_4$ to $c_5$ . So no issues here.

Similar arguments hold for $n > 3$ .

Now for $c_2$ , the only issue is if we have $c_2 + c_4$ , and we place a singular $c_3$ .
We will show this never happens.
Indeed suppose that it did. The only way for this to occur is to start with no terms with index less than $5$ , place $c_2$ , place a singular $c_3$ , place a $c_2$ , and then place a singular $c_3$ again, and place $c_2$ . This means that $x$ increments by $5$ and $y$ increments by $2$ . But
$\left \lfloor \frac{x + 5}{\phi} \right \rfloor + \left \lfloor \frac{x}{\phi} \right \rfloor \ge 3.$ This is a contradiction.

Suppose $-1 < x - \phi y < 0$ . Then for each fixed $y$ , there is a unique $x$ which satisfies the inequality. This is, of course,
$-1 + \phi y < x < \phi y \implies x = \lfloor \phi y \rfloor.$
Now whenever $y$ increments by $1$ , $x$ increments by either $1$ or $2$ .
Again note we can set $y$ and $x$ to have no terms for now.
If we add $c_2$ to $y$ , we have $x$ incrementing by $1$ . If we add $c_3$ to $y$ , we have $x$ incrementing by $2$ .
Now $x$ can only increment by $2$ at most twice in a row, since $3\phi < 5$ . $x$ can only increment by $1$ once at a time since $2\phi > 3$
We apply the same process; the proofs for $c_n$ for $n > 2$ are analogous. It suffices to show that having 3 $c_2$ placements and 2 $c_3$ placements (in a row) is impossible; what this means is we have $x$ incrementing by $7$ and $y$ incrementing by $5$ .
However,
$\lfloor \phi y + 5\phi \rfloor - \lfloor \phi y \rfloor \ge 8,$ since $5\phi > 8$ .

For the last case $-1 - \phi < x - \phi y < - \phi$ , we let $x$ determine a fixed $y$ . Note $(0,1)$ can be attained by adding $c_0$ to $y$ , and we are done by the first process.

Whew.

This post has been edited 1 time. Last edited by popop614, Jan 9, 2024, 4:47 PM
Reason: oops

Z K Y

The post below has been deleted. Click to close.

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

7586 posts

#12 h Mar 17, 2025, 8:31 PM

Y by

quite a few annoyingish small details to handle, time to see if i can write something waterproof

Let $\phi$ be the golden ratio. The desired inequality, scaled so that $\alpha=1$ , is $-\phi-1<x-\phi y<\phi$ .

Here is the easier part first. From Binet's and some calculation to figure out the exact shift of the indices, we get
$c_n=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}{\sqrt{5}}$ and we find $c_n-\phi c_{n-1}=\left(\frac{1-\sqrt{5}}{2}\right)^{n-2}$ .

Now any pair $(x,y)$ formed by the definition in the problem necessarily has $x-\phi y$ to be a sum of expressions $c_n-\phi c_{n-1}$ for distinct values $n\ge 1$ . In particular, the minimal value (which will not be achieved) is formed by the infinite geometric sum
$\left(\frac{1-\sqrt{5}}{2}\right)^{-1}+\left(\frac{1-\sqrt{5}}{2}\right)^{1}+\left(\frac{1-\sqrt{5}}{2}\right)^{3}+\dots=-\phi-1$ and the maximal value is achieved by
$\left(\frac{1-\sqrt{5}}{2}\right)^{0}+\left(\frac{1-\sqrt{5}}{2}\right)^{2}+\left(\frac{1-\sqrt{5}}{2}\right)^{4}+\dots=\phi$ thus yielding the desired inequality. (it's $x-\phi y$ due to the fact that $x\div y\approx \phi$ )

Now we'd like to show that any pair $(x,y)$ satisfying the inequality can be represented. The main idea is to use a greedy algorithm, and induct down. There are two cases.

Case 1: The largest pair $(c_n,c_{n-1})$ to take out of $(x,y)$ is of the form $(c_{2n+1},c_{2n})$ for $n\ge 0$ .

wip

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a