2 Pandean sequences, flutes and the Fibonacci sequence
A sequence \((a_k)\), indexed by \(\mathbb {N}^*\) and consisting of positive integers is called pandean if \(a_1 = 1\) and if, for every \(k {\gt} 1\), we have
Given a pandean sequence \((a_k)\), if there exists a positive integer \(n\) such that \(a_k = a_{k+n-1}\) for all \(k\in \mathbb {N}\), the tuple \((a_1, \ldots , a_n)\) is called a Pan flute, or simply a flute, of height \(n\). The set of all flutes of a given height \(n\) is denoted Flute\((n)\).
Note that in a flute of height \(n\), the first and last entries are equal to \(1\).
For any positive integer \(n\), the set Flute\((n)\) is non-empty.
It is clear that the constant sequence consisting entirely of ones is pandean, and such a pandean sequence gives rise to a flute of height \(n\) for any \(n\).
Recall that the Fibonacci sequence \((F_k)_{k \in \mathbb {N}}\) is defined by \(F_0 = 0, F_1 = 1\) and the recursive formula
1) If \(n\) is odd, the \(n\)-tuple
is a Pan flute of height \(n\).
2) If \(n\) is even, the \(n\)-tuple
is a Pan flute of height \(n\).
These are a tedious but straightforward calculation.
In a flute \((a_1, \ldots , a_n)\), one of the following two statements holds.
1) \(a_2 = 1\) or \(a_{n-1} =1\).
2) There exists an index \(i \in \{ 2,\ldots , n-1\} \) such that \(a_i = a_{i-1} + a_{i+1}\).
Suppose that 1) does not hold. In particular, \(a_2 - a_1 {\gt} 0\) and \(a_n - a_{n-1} {\lt} 0\). We prove that statement 2) holds by contradiction. Thus, assume that for all \(i \in \{ 2,\ldots , n-1\} \), we have \(a_i \neq a_{i-1} + a_{i+1}\). Since the \(a_i\) are positive integers, we necessarily have \(a_{i-1} + a_{i+1} \geq 2 a_i\) for all \(i \in \{ 2,\ldots , n-1\} \). Thus, for a given \(i\), we have
Gathering these inequalities, we obtain
which contradicts the fact that \(a_n - a_{n-1} {\lt} 0\).
Fix a positive integer \(n\), and let \((a_1, \ldots , a_n) \in {\rm Flute}(n)\). For any \(i \in \{ 1,\ldots , n\} \), we have \(a_i \leq F_n\).
Consider the statement
The proposition claims that \(P_n\) holds for all \(n \in \mathbb {N}^*\). We prove this by induction on \(n\). The base case \(n = 1\) is clear, since the only flute of height \(1\) is \((1)\), and \(F_1 = 1\). Similarly, the case \(n = 2\) is clear, since the only flute of height \(2\) is \((1,1)\), and \(F_2 = 1\). Now, assume that \(P_k\) holds for all \(k\) up to and including a fixed \(n \in \mathbb {N}^*\). Let \((a_1, \ldots , a_{n+1}) \in {\rm Flute}(n+1)\). By Lemma 2.4, we have either \(a_2 = 1\) or \(a_n = 1\), or there exists an index \(i \in \{ 2,\ldots , n\} \) such that \(a_i = a_{i-1} + a_{i+1}\). Suppose that \(a_2 = 1\). Then \((a_1, a_3, \ldots , a_{n+1}) \in {\rm Flute}(n)\), and so by the induction hypothesis, \(a_i \leq F_n\) for all \(i \in \{ 1,\ldots , n\} \). Since \(F_n \leq F_{n+1}\), we have \(a_i \leq F_{n+1}\) for all \(i \in \{ 1,\ldots , n\} \). A similar argument applies if \(a_n = 1\). Now, suppose that there exists an index \(i \in \{ 2,\ldots , n\} \) such that
We claim that \((a_1, a_2, \ldots , a_{i-1}, \widehat{a_i}, a_{i+1}, \ldots , a_{n+1}) \in {\rm Flute}(n)\), where \(\widehat{a_i}\) means we omit \(a_i\). Again by the induction hypothesis, we have that
It remains to show that \(a_i \leq F_{n+1}\). To see this, note that 1 and 2 together imply it is sufficient to show that either \(a_{i-1}\) or \(a_{i+1}\) is bounded above by \(F_{n-1}\). But recall that \(a_{i-1}\) and \(a_{i+1}\) both belong to the flute \((a_1, a_2, \ldots , a_{i-1}, \widehat{a_i}, a_{i+1}, \ldots , a_{n+1}) \) of height \(n\). Thus, the conditions of Lemma 2.4 apply to this flute, so that by a reduction argument identical to the one above, there exists a flute of height \(n-1\) containing either \(a_{i-1}\) or \(a_{i+1}\) (or both !), whereby at least one of the two is bounded above by \(F_{n-1}\). This completes the induction step, and the proposition follows.