The story started when I was told to apply for PROMYS India and to submit my application, I would have to solve or attempt a problem set.

When I opened the problem set, the first problem immediately gained my attention. I have submitted my application, and this article is my documentation of the solution I gave, or atleast my attempt (if it may turn out that my solution was wrong) on the problem. And of course I will be adding my remarks about what things could be improved, and the things I didn't think of back then.

---

So the problem states the following:

Start with a positive integer, then choose a negative integer. We'll use these two numbers to generate a sequence using the following rule: create the next term in the sequence by adding the previous two.

(a) Can you find a sequence of this type that starts with 5 elements that alternate sign? With 10 elements that alternate sign? Can you find a sequence with any number of elements that alternate sign?

(b) Given a particular starting integer, what negative number should you choose to make the alternating part of the sequence as long as possible? For example, if your sequence started with 8, what negative number would give the longest alternating part? What if you started with 10? With n?

---

In this article we will cover the first part (a) of the above problem.

Now an example of such a sequence can be:
\(5, -3, 2, -1, 1, 0, ...\)

We don't actually count 0 as an alternating term, so the above sequence is said to contain 5 alternating terms.

Now my solution actually doesn't have complete proofs and many the statements and results are based on the patterns I found but now the fun begins!

So what we can guess or maybe what our gut feeling says is that the above sequence is closely related to the fibonacci sequences we know of, right?

Let us denote the starting positive integer by \(p\), \(p \in N\)
and by \(-n\) the starting negative integer, \(n \in N\);

The sequence so formed by our chosen starting number is thus:
\(p, -n,p-n,p-2n,2p-3n,3p-5n,5p-8n,8p-13n,13p-21n,21p-34n,34p-55n,...\)

And what we observe here is that, the coefficients are actually terms of the fibonacci sequence!

Consider the fibonacci sequence:
\(0,1,1,2,3,5,8,13,21,34,55,...\)
We will make use of this as we move one and try to identify a pattern.

As we are dealing with getting starting elements to alternate their signs, we know that our sequence's first term is p, which is positive, and the second term is -n, which is negative.
So suppose we need to alternate the signs of the following terms.
This means, we have to get the third term to be negative and fourth term to be positive and so on..

As the third term is negative:

or we can say that the ratio of p to n is greater than 1
Now, for fourth term to be positive, we have:

So we can basically say that the ratio of \(p\) to \(n\) is less than 2

So let us actually define this ratio of \(p\) to \(n\) as the bounding ratio and obviously this bounding ratio depends on the context, like for inequality (1) the bounding ratio is 1, and for inequality (2) it is 2.

The actual definition of the bounding ratio may be: the ratio of \(p\) to \(n\) must be greater than the bounding ratio or less than the bounding ratio for the inequality involving only \(p\) and \(n\) to hold.

This maybe confusing at first, but it will be very clear as we proceed.

So to get the third term of our sequence i.e. \(p-n\) to be positive, the ratio of \(p\) to \(n\) must be greater than the bounding ratio of 1, and similarly to get the fourth term i.e. \(p-2n\) to be positive, the ratio of \(p\) to \(n\) must be less than the bounding ratio of 2

Do not forget that we want the terms to alternate their signs which is why we need the inequalities to hold!

---

• Bounding ratios

Let us write down some inequalities for following terms to alternate their signs:

So now, to have atleast 3 alternating terms, we must have inequality (3) to hold.
and to have atleast 4 alternating terms, we would need inequality (4) to hold, but do not forget that (3) must also hold!

Let us now try to generate a sequence with exactly 5 alternating terms.
So inequality (5) must hold, but (4) is also needed to hold otherwise we won't even have 4 alternating terms.

Thus we have:
\(p \lt 2n\) and \(p \gt 1.5n\)

We will study two cases:

Pick \(n\) to be 4, we thus have:
\(p \lt 8\) and \(p \gt 6\), thus the only choice we have is to pick \(p = 7\).
The sequence so obtained is:
\(7,-4,3,-1,2,1,3,4,7,11,...\)

For our other case, pick \(n\) to be 8, we have:
\(p \lt 16\) and \(p \gt 12\)
Suppose we pick \(p = 13\), then the sequence generated is:
\(13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2,...\)
But didn't we just need five alternating terms, but we have seven!
The reason is that, for our chosen values of \(p\) and \(n\) inequality (6) and (7) also hold! Thus getting us seven alternating terms instead of exactly five.

So as we analysed the above sequences, it is quite easy to conclude that to have exactly 5 alternating terms, inequality (4) and (5) should hold, but (6) should not hold!

So we can actually say,
\(p \lt 2n\) and \(p \gt \tfrac{3}{2}n\) and \(p \ge \tfrac{5}{3}n\)
Choosing \(n\) to be any arbitary large number, 12 (say), then we have,
\(p \lt 24\) and \(p \gt 18\) and \(p \ge 20\).
For \(p = 20\), we obtain the following sequence:
\(20, -12, 8, -4, 4, 0, 4, 4, 8, ...\) which contains exactly 5 alternating terms!
Choosing \(p = 19\) which does not satisfy \(p \ge 20\), our sequence generated is:
\(19,-12,7,-5,2,-3,-1,-4,-5...\)
Which clearly contains more than 5 terms that alternate their signs!


Remember at the very beginning we identified a pattern, that the coefficients of p and n in the sequence are the terms of the Fibonacci sequence. Now seems to be the right idea to take a look into it!

Let us define a Fibonacci sequence, \(F_1 = 0, \thinspace F_2 = 1, \thinspace F_3 = 1\thinspace\) and \(F_n = F_{n-2} + F_{n-1}\)

The sequence is as follows:
\(0,1,1,2,3,5,8,13,21,34,55,...\)

Let us now list some bounding ratios of \(p\) to \(n\),

for 3 terms with alternating signs:
the ratio \(p\) to \(n\) must be more than the bounding ratio of \(1\)

for 4 terms with alternating signs:
the ratio \(p\) to \(n\) must be less than the bounding ratio of \(\tfrac{2}{1}\)

for 5 terms with alternating signs:
the ratio \(p\) to \(n\) must be more than the bounding ratio of \(\tfrac{3}{2}\)

for 6 terms with alternating signs:
the ratio \(p\) to \(n\) must be less than the bounding ratio of \(\tfrac{5}{3}\)


Notice any pattern? The bounding ratio is exactly equal to the quotient of two consecutive Fibonacci terms, more importantly, for 3 terms to alternate the signs, the bounding ratio is \(\tfrac{F_3}{F_2}\) and for 4 terms to alternate the signs, the bounding ratio is \(\tfrac{F_4}{F_3}\), and it goes on!

Also note that the bounding ratio increases and decreases alternatively, For example, for 3 alternating terms, the ratio is \(1\), which increases to \(2\) for 4 alternating terms and then again decreases to \(1.5\) for 5 alternating terms, and so on...
This means that bounding ratio increases when odd number of alternating terms is increased by 1 to get an even number of alternating term.
For example, when there are 3 alternating terms, the ratio is \(1\), when the terms are 4, the ratio increases to \(2\).
Similarly when there are 6 alternating terms, the ratio is \(\tfrac{5}{3} = 1.66...\) which decreases to \(\tfrac{8}{5} = 1.6\) when there are 7 alternating terms.
We also observe that for even number of terms with alternate signs, the ratio of \(p\) to \(n\) is less than the bounding ratio, and for odd number of terms with alternate signs, the ratio of \(p\) to \(n\) is more than the bounding ratio, where by our observation, the bounding ratio for \(k\) alternating terms is \(\tfrac{F_k}{F_{k-1}}\)
Now we know the exact bounding ratios, so we should be able to directly use this knowledge and figure out the required values of \(p\) and \(n\), right?

---

• Generalizing

Suppose we want to get exactly \(k \in N\) starting terms that alternate their sign.
If say, \(k\) is an even number, then from the above observations:

As we have analysed for 5 alternating terms that inequality (3) and (4) should hold but (5) mustn't hold! Similar is the case here also.
As we see that (11), (12) and (13) should hold, but as we have observed that bounding ratio decreases from (12) to (13) i.e.,
\(\tfrac{F_{k+1}}{F_{k}} \lt \tfrac{F_{k}}{F_{k-1}}\)

Thus (13) is stronger than (12), so only (11) and (13) should hold, as when (11) and (13) holds, (12) also holds!

If say, \(k\) is an odd number, then,

We have, (14), (15) and (16) should hold, but as bounding ratio is increaing from (15) to (16) i.e.,
\(\tfrac{F_{k+1}}{F_{k}} \gt \tfrac{F_{k}}{F_{k-1}}\)

Thus (16) is stronger than (15), so only (14) and (16) should hold, as when (14) and (16) holds, (15) also holds!

We also have the general formula for the \(k^{th}\) term of our Fibonacci sequence:

and the bounding ratio \(B_{0}\) for \(k-1\) alternating terms is given by:

and the bounding ratio \(B_{1}\) for \(k\) alternating terms is given by:

and the bounding ratio \(B_{2}\) for \(k+1\) alternating terms is given by:

So now, the two cases we have are:
If \(k\) is odd, then

and if \(k\) is even, then

This finally leads us to the answers we are looking for.

For generating a sequence with 10 starting terms that alternate signs, we have:
\(B_0 = \tfrac{F_{10-1}}{F_{10-2}} = \tfrac{21}{13}\)

\(B_1 = \tfrac{F_{10}}{F_{10-1}} = \tfrac{34}{21}\)

\(B_2 = \tfrac{F_{10+1}}{F_{10}} = \tfrac{55}{34}\)

Since 10 is even, so we have:
\(\tfrac{p}{n} \gt B_0\), \(\tfrac{p}{n} \lt B_1\) and \(\tfrac{p}{n} \le B_2\)

So we finally have:
\(\tfrac{p}{n} \gt \tfrac{21}{13}\) and \(\tfrac{p}{n} \le \tfrac{55}{34}\)

For quick calculation, choose \(n = 13 \times 34\)

We can only choose \(p\) to be 715 and the sequence generated is:
\(715, -442, 273, -169, 104, -65, 39, -26, 13, -13, 0, -13, -13, -26, ...\)

and this clearly has 10 alternating terms!

Now we can definitely get as many alternating terms as we please, but let us try to find a quicker way.
Let us try to find/generate a sequence with 12 terms that alternate signs.
So,

\(B_0 = \tfrac{F_{12-1}}{F_{12-2}} = \tfrac{55}{34}\)

\(B_1 = \tfrac{F_{12}}{F_{12-1}} = \tfrac{89}{55}\)

\(B_2 = \tfrac{F_{12+1}}{F_{12}} = \tfrac{144}{89}\)

and \(\tfrac{p}{n} \gt B_0\), \(\tfrac{p}{n} \lt B_1\) and \(\tfrac{p}{n} \le B_2\)

So we finally have:
\(\tfrac{p}{n} \gt \tfrac{55}{34}\) and \(\tfrac{p}{n} \le \tfrac{144}{89}\)

Now if we choose \(n = 89 \times 34\), we have:
\(p \gt 4895 \) and \(p \le 4896\),
and these two numbers differ exactly by 1!

When we tried to generate a sequence with 10 alternating terms, we came across the following inequality [(18) and (19)]
\(p \gt 714\) and \(p \le 715\)
Here also we see that 714 and 715 differ exactly by 1

This must have something to do with how we are choosing \(n\).

As for exactly \(k\) alternating terms, we have:

where the ratio of \(p\) to \(n\) is greater than (or less than) \(B_0\) and less than equal to (or greater than equal to) \(B_2\) as the latter inequality is always stronger than inequality involving \(B_1\).

So as we choose \(n = F_k \times F_{k-2}\), we obtain:
\(p \gt B_0 \times n\) or (\(p \lt B_0 \times n\))
\(p \le B_2 \times n\) or (\(p \ge B_2 \times n\))

and we notice that, \(B_2 \times n - B_0 \times n = 1\)
or we can say that:
\(F_{k+1}\times F_{k-2} - F_{k-1} \times F_{k} = 1\)

Let us verify if this holds for all Fibonacci terms or not!
\(0,1,1,2,3,5,8,13,21,34,55,...\) is our Fibonacci sequence

Choose \(k = 7\), then \(F_8 \times F_5 - F_6 \times F_7 = 13*3 - 5*8 = -1\)
Choose \(k = 8\), then \(F_9 \times F_6 - F_7 \times F_8 = 21*5 - 8*13 = 1\)

So it suggest that, \(F_{k+1}\times F_{k-2} - F_{k-1} \times F_{k} = 1\) when \(k\) is even, and
\(F_{k+1}\times F_{k-2} - F_{k-1} \times F_{k} = -1\) when \(k\) is odd.

Which makes sense as when \(k\) is even, the ratio \(p\) to \(n\), is less than equal to \(B_2\) and so it would mean, \(B_2 \gt B_0\), and when \(k\) is odd, the ratio \(p\) to \(n\), is less than \(B_0\) but greater than \(B_2\) which means \(B_0 \gt B_2\)

---

• Final move

So at last we are left with two cases:
To generate a sequence with a positive integer \(p\) and a negative integer \(-n\), which contains exactly \(k\) terms which alternate signs:

define,

Case 1: If \(k\) is even,
choose \(n = F_{k-2} \times F_{k}\),
then, \(p \gt B_0 \times n\) and \(p \le B_2 \times n\)
Only \(p = F_{k+1} \times F_{k-2}\) satisfies the above inequality.
So,

Case 2: If \(k\) is odd,
choose \(n = F_{k-2} \times F_{k}\),
then, \(p \lt B_0 \times n\) and \(p \ge B_2 \times n\)
Only \(p = F_{k+1} \times F_{k-2}\) satisfies the above inequality.
So,

Notice anything?? The results of both the cases are same and have nothing to do with whether \(k\) is even or odd!

Therefore,
with,

We can generate a sequence with exactly \(k\) alternating terms!
where, \(F_1 = 0, F_2 = 1, F_3 = 1\) and \(F_n = F_{n-2} + F_{n-1}\)

and by the way you always get a free zero!