Reason behind periodic patterns in the Fibonacci polynomial sequence when expressed in terms of a natural number

Question

A while back, a friend of mine had challenged me to decipher the pattern within the following sequence:

1, 5, 11, 19, 29, ...

Staring at it for some time, the first thing that jumped at me was that each of the terms was very close to a multiple of 6. That is, the series could be rewritten as thus:-

(6 * 0 + 1), (6 * 1 - 1), (6 * 2 - 1), (6 * 3 + 1), (6 * 5 - 1), ...

I had my suspicions as to what the pattern was, but I couldn't be sure. So, I searched for the sequence in the OEIS and this is what I got: the terms of the Fibonacci polynomial ($n^2 - n - 1$) starting from the $3$rd position matched with this sequence. I was very confused as to how these two (seemingly) very unrelated means produced the same result, but at least I had gotten the proceeding terms, so I chose to ignore this for the time being. Here are the first $20$ terms of the sequence(s) I got:-

1, 5, 11, 19, 29, 41, 55, 71, 89, 109, 131, 155, 181, 209, 239, 271, 305, 341, 379, ...

Rewriting this sequence in terms of 6, we get the following result:-

6   *   0   +   1   =   1
6   *   1   -   1   =   5
6   *   2   -   1   =   11
6   *   3   +   1   =   19
6   *   5   -   1   =   29
6   *   7   -   1   =   41
6   *   9   +   1   =   55
6   *   12  -   1   =   71
6   *   15  -   1   =   89
6   *   18  +   1   =   109
6   *   22  -   1   =   131
6   *   26  -   1   =   155
6   *   30  +   1   =   181
6   *   35  -   1   =   209
6   *   40  -   1   =   239
6   *   45  +   1   =   271
6   *   51  -   1   =   305
6   *   57  -   1   =   341
6   *   63  +   1   =   379
...

Here, two patterns can be observed, the first one being noticeable in the list of multipliers:-

 0
 +  1   =   1
 +  1   =   2
 +  1   =   3   [Difference += 1]
 +  2   =   5
 +  2   =   7
 +  2   =   9   [Difference += 1]
 +  3   =   12
 +  3   =   15
 +  3   =   18  [Difference += 1]
 +  4   =   22
 +  4   =   26
 +  4   =   30
 ...
 

Notice how the difference between successive multipliers increases by $1$ after every $3$ terms. The second pattern is how the augends alternate between $+1$ and $-1$ in the order $+1, -1, -1, +1, -1, -1, +1, ...$

I then thought about doing the same thing for natural multiplicands other than 6 as well. I have combined all the results for numbers 1 to 15 along with the code I wrote for the task in this GitHub Repository. I would highly encourage you to see the results because they are genuinely interesting.

So, finally, my question is, what is the cause of these patterns showing up -- these periodic oscillations between the augends and the recurrent progression of the multipliers (mainly for 6, but also for the other naturals)? Also, how is the sequence of fibonacci polynomial related to all of this?

All insights are incredibly appreciated and thank you so much for reading.

Answer 1

Take a second degree polynomial sequence, i.e. $an^2+bn+c$. Take the difference between consecutive terms, you'll get a linear sequence: $2an+a+b$. Take the difference once more, you get a constant: $2a$.

So a second degree polynomial sequence can be considereed as the partial sums of a linear sequence. Dividing by $6$ or any other number $p$, makes no difference to that.

But then, you want integers, rather than rationals, for the multipliers and the augends. Reasoning modulo $p$, this rounding creates a pattern of length $p$, hence the smallest pattern length (the period) is a divisor of $p$. In the example you propose, $a=1, b=-1$, so the linear sequence is $2n$. This implies that all elements have same parity (odd, because $c=-1$ is odd). We then consider $\frac {n^2-n} 2$ which is always integer, and dividing it by $3$ is the same (up tp a constant) as dividing your original sequence by $6$, which explains why the period is $3$.

For this reason, I presume the original sequence can always be expressed as $p m_n + r_n$, where $(m_n)$ and $(r_n)$ are integers, $(r_n)$ has period $p$ or a divisor, and $m_{n+1}-m_n = q_n$ where $(q_{n+1}-q_n)$ has also period $p$ or a divisor - and in addition, when $p$ is even, periods are $\frac p 2$ or a divisor. But I have not proven all that.

Note that for a given $p$, there are multiple ways of choosing the sequences $(m_n)$ and $(r_n)$, which explains why you get a period $8$ for $p=8$, while I bet a period $4$ is possible. For this, you can use your GitHub software to study $\frac {n^2-n} 2$ (which are integers) divided by $4$, get a result with periods $4$, then deduce a result with periods $4$ for $n^2-n-1$.