Why is a=43 an exception?

Question

There is a sequence. The first integer is positive, the second integer is negative. An alternating part is a part that switches between positive and negative (0 is not included)

(a) I have a complete answer to this part

(b) What second term should be chosen to get the longest possible switching between positive and negative

For b, I wrote an entire proof as to why, assuming a is the positive first integer, b is the integer closest to -0.618a. However, I was testing cases today, and I found that a=43 is an exception to this. 0.618 multiplied by a would be -26.57 something, which is about -27. However, the number to make the sequence the longest is actually -26.

Could anyone give me a hint as to why this happened?

Answer 1

You have posed an interesting question here, but have not shown how you got to where you are. If you look at a previous link of mine, you'll find a general solution to the problem $f_n=f_{n-1}+f_{n-2}$ with arbitrary initial conditions, say $f_0$ and $f_1$, or $a$ and $b$ in your notation. It easy to show that your solution can be expressed as

$$ f_n=\bigg(b-\frac{a}{2}\bigg)F_n+\frac{a}{2}L_n $$

where $F_n$ and $L_n$ are the Fibonacci and Lucas numbers, respectively. Here you can see that the Fibonacci terms are always negative while the Lucas terms are all positive (for $a>0$ and $b<0$).

This can also be expressed as

$$ f_n=bF_n+aF_{n-1} $$

Now, we can express the Fibonacci number with the Binet formula as follows

$$ F_n=\frac{\varphi^n-\psi^n}{\varphi-\psi} $$

where $\varphi$ is the golden ratio and $\psi=1-\varphi$. Thus

$$ f_n=\frac{b(\varphi^n-\psi^n)+a(\varphi^{n-1}-\psi^{n-1})}{\varphi-\psi} $$

Almost there. For large $n$ we have $\varphi^n>>\psi^n$ and the above becomes

$$ f_n\approx\frac{\varphi^{n-1}}{\varphi-\psi}(b\varphi+a) $$

From this we can see that if $\ b\varphi+a=0$, $\ f_n\to 0$ for large $n$. In fact, I tried this numerically, and it seems to oscillate forever. Now, if $\ b\varphi+a<0$, then the negative terms dominate and the series goes negative. Likewise, if $\ b\varphi+a>0$, then the series goes positive.

To sum up, the point is the criterion you found, i.e., $\ b\varphi+a=0$ for determining the value of $b$ that gives the longest oscillation, is only approximate. However, if you allow non-integer values of $b=-a/\varphi$, then you can oscillate forever.

Answer 2

It is easy to verify that the smallest values for $A$ and $B$ that yield a certain number of alternating values, are found when the series ends with $(1, -1)$. Working backwards the optimal pairs $(A, B)$ are given by: $(1, -1)$, $(2,-1)$, $(3, -2)$, $(5, -3)$, $(8, -5)$, $(13,-8)$, $(21, -13)$, $(34, -21)$, $(55,-34)$, $(89,-55)$. One will notice that these are the Fibonacci numbers.

If you start with some other value for $A$, the number of oscillations is always smaller. This is in particular true when $B$ differs by roughly $0.5$ from the optimal value. The rounding up or down is not always logical. I found eight cases for $A \le 100$ where $B$ had to be rounded differently than one would expect. Here they are:

$(4, -3)$ where the value $2.472$ was rounded up

$(9, -5)$ where the value $5.562$ was rounded down

$(25, -16)$ where the value $15.451$ was rounded up

$(43, -26)$ where the value $26.575$ was rounded down

$(48, -29)$ where the value $29.666$ was rounded down

$(51, -31)$ where the value $31.520$ was rounded down

$(64, -39)$ where the value $39.554$ was rounded down

$(93, -58)$ where the value $57.477$ was rounded up