Tribonacci and higher-order sequences

Tribonacci, tetranacci, pentanacci, k-generalized Fibonacci, Padovan, Perrin and Narayana sequences, dominant roots and Binet forms.

• Cubic analogues of Lucas sequences
• Fibonacci p-numbers
• Generalized Padovan–Perrin recurrences
• k-generalized Fibonacci numbers
• k-generalized Lucas numbers
• Leonardo p-numbers
• Padovan and Perrin sequences
• Self-convolutions of m-step Fibonacci numbers
• Sums of squares of Tribonacci and Tetranacci numbers
• Tetranacci and pentanacci numbers
• Tribonacci numbers
• Zeta functions of generalized Fibonacci numbers

TheoremGeneralized Pell numbers count compositions with two-colored ones#✓fully proved

Let \(k \ge 2\) and \(n \ge 1\) be natural numbers, and let \((P_m)_{m \in \mathbb{Z}}\) be natural numbers with \(P_m = 0\) for \(2 - k \le m \le 0\), \(P_1 = 1\), and \(P_m = 2P_{m-1} + P_{m-2} + \dots + P_{m-k}\) for all \(m \ge 2\). Then the number of compositions of \(n\) into parts from \(\{1, \dots, k\}\), where each part equal to \(1\) carries one of two colors, equals \(P_{n+1}\).

theorem generalized_pell_eq_two_colored_compositions
    (k n : ℕ) (hk : 2 ≤ k) (hn : 1 ≤ n)
    (P : ℤ → ℕ)
    (hPzero : ∀ m : ℤ, 2 - (k : ℤ) ≤ m → m ≤ 0 → P m = 0)
    (hPone : P 1 = 1)
    (hPrec : ∀ m : ℤ, 2 ≤ m →
      P m = 2 * P (m - 1) +
        ∑ i : Fin (k - 1), P (m - (((i : ℕ) : ℤ) + 2))) :
    Set.ncard {
      c : Σ ℓ : Fin (n + 1), Fin ℓ → Fin (k + 1) |
        ∑ j : Fin c.1, (if (c.2 j).val ≤ 1 then 1 else (c.2 j).val) = n
    } = P ((n + 1 : ℕ) : ℤ)

Sources

• Jhon J. Bravo, Jose L. Herrera, and José L. Ramírez, "Combinatorial Interpretation of Generalized Pell Numbers," Journal of Integer Sequences 23 (2020), Article 20.2.1, theorem C_k(n) = P_{n+1}^{(k)} for n ≥ 1, lines 441–447, https://cs.uwaterloo.ca/journals/JIS/VOL23/Bravo/bravo4.tex.

DefinitionNarayana's cows sequence#✓fully proved

The sequence \((N_n)_{n \ge 0}\) of natural numbers defined by \(N_0 = 0\), \(N_1 = N_2 = 1\) and \(N_n = N_{n-1} + N_{n-3}\) for \(n \ge 3\).

def narayanaCowsSequence : Nat → Nat
  | Nat.zero => Nat.zero
  | Nat.succ Nat.zero => Nat.succ Nat.zero
  | Nat.succ (Nat.succ Nat.zero) => Nat.succ Nat.zero
  | Nat.succ (Nat.succ (Nat.succ n)) =>
    narayanaCowsSequence (Nat.succ (Nat.succ n)) + narayanaCowsSequence n

Used by 6

Used byArndt compositions with parts at most 4 and Narayana's cows sequence · Logarithmic bounds for Narayana numbers that concatenate two repdigits · Narayana numbers that concatenate two repdigits in bases 2 to 9 · Infinitely many Narayana numbers are Sierpiński numbers · Narayana numbers that are Riesel numbers · Rampersad–Wiebe Theorem 7

2 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.