Start with this triangle (OEIS A118981). This triangle is simple to generate with the following recurrence relation (though $T(0,0)$ ends up different from the OEIS version): $$ T(0,0) = 2;T(1,0) = 1;T(1,1) = 1; $$ $$T(n,k) = T(n-1, k) + T(n-1, k-1) + T(n-2, k-2), n>1 $$

The sequence in question is generated by taking the largest element from each row, then dividing it by the row number $n$. The resulting sequence is as follows (listed up to $a_{20}$):

$1, 1.5, 2, 3, 5, 10, 19, 37, 77.\overline 7, 158, 331, 715, 1505, 3287, 7224.4, 15529, 34839, 77453.8 \overline3, 168950, 386050, ...$

My question is: Why are the majority of these numbers convoluted convolved Fibonacci numbers? Even the ones which are not integers become convoluted convolved Fibonacci numbers when rounded down to the nearest integer. Some examples:

$$floor(a_{15}) = 7224 = G_{11}^{(5)}$$ $$a_{16} = 15529 = G_{12}^{(5)}$$ $$a_{17} = 34839 = G_{12}^{(6)}$$ $$a_{19} = 168950 = G_{13}^{(7)}$$ $$a_{20} = 386050 = G_{14}^{(7)}$$ $$floor(a_{21}) = 865264 = G_{15}^{(7)}$$


1 Answer 1


We have $$T(n,k) = [x^ny^{n-k}]\ \frac{2 - (1+y)x}{1-(1+y)x-x^2}=[y^{n-k}]\ L_n(1+y),$$ where $L_n$ is the $n$-th Lucas polynomial.

For $k<n$, we have an explicit formula: \begin{split} T(n,k) &= \sum_{i=0}^{\lfloor n/2\rfloor} \frac{n}{n-i}\binom{n-i}i \binom{n-2i}{n-k}\\ &= \frac{n}{n-k}\sum_{i=0}^k \binom{n-i-1}{k-i} \binom{k-i}i\\ &=\frac{n}{n-k} F_{k+1}^{(n-k)}. \end{split} So, relation to convoluted Fibonacci numbers should come at no surprise.

In the given examples for $G_{j+1}^{(r)}$ with $3\nmid n$, we have $\gcd(r,j)=1$, implying that $G_{j+1}^{(r)} = \frac1r F_{j+1}^{(r)}$.

Numerical evidence suggests that for a fixed $n$, $T(n,k)$ is unimodal and achieves its maximum at $k=n-\left\lfloor \frac{n}3\right\rfloor$, suggesting that $$\frac1n\max_k T(n,k) = \frac1{\lfloor n/3\rfloor} F_{n-\lfloor n/3\rfloor + 1}^{(\lfloor n/3\rfloor)} \stackrel{3\nmid n}{=} G_{n-\lfloor n/3\rfloor + 1}^{(\lfloor n/3\rfloor)}.$$

The case $3\mid n$ can be addressed similarly.

  • $\begingroup$ Thanks for this! As a follow up, is it provable that for a fixed n, T(n,k) is unimodal and/or that it achieves its maximum at $k=n−⌊n_3⌋$ ? $\endgroup$
    – Mitch
    Oct 11, 2021 at 19:16
  • $\begingroup$ I believe it is, but I did not think much. $\endgroup$ Oct 11, 2021 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.