Why are Fibonacci-resistant numbers the golden rectangle numbers?

131 Views Asked by At

Let ${}_{1,1}f_n$ be the $n$-th Fibonacci number, where the $1,1$ subscript indicates the sequence starts with $1,1,2,3,5,8,13,\ldots$. So the Lucas numbers are ${}_{2,1}f_n$, leading to $2,1,3,4,7,11,\dotsc$.

Consider all ${}_{a,b}f_n$ with $a,b \ge 1$. There is no $a,b$ initial pair that leads to ${}_{a,b}f_4 = 2$, but every number $> 2$ can be realized as ${}_{a,b}f_4$ for some $a,b$. There is no $a,b$ initial pair that leads to ${}_{a,b}f_5 = 6,$ but every number $> 6$ can be realized as ${}_{a,b}f_5$ for some $a,b$. So these numbers are somehow "Fibonacci-resistant."

Define $g(k)$ to be the largest $m$ such that here is no $a,b$ that leads to ${}_{a,b}f_k = m$, but all numbers $>m$ are so realizable. $$g(3), g(4), g(5), \ldots, g(10) = 1, 2, 6, 15, 40, 104, 273, 714 \;.$$ These are the "golden rectangle numbers," A001654: $$g(k) = F(k-2) \cdot F(k-1) \;,$$ where $F(k)$ is the $k$-th Fibonacci number: e.g., $g(5) = F(3) \cdot F(4) = 2 \cdot 3 = 6$; $g(6) = 3 \cdot 5 = 15;$ etc.

Q. Why are these numbers $g(k)$ the golden rectangle numbers?

1

There are 1 best solutions below

1
On BEST ANSWER

In effect, since the recurrence is linear and homogeneous, your ${}_{a,b}f_n=a\cdot{}_{1,0}f_n+b\cdot{}_{0,1}f_n=a\cdot F(n-2)+b\cdot F(n-1)$.

Since the adjacent Fibonacci numbers are coprime, any number above certain threshold can be expressed in this form. The greatest number that can't is the Frobenius number of $F(n-1)$ and $F(n-2)$. Its properties are pretty well known.

Don't be confused by the formula $xy-x-y$; it was derived under the assumption $a,b\ge0$. If you insist on $a,b\ge1$, it will turn into $xy$.