Lucasnomial Fuss–Catalan numbers

TheoremIntegrality of generalized Lucasnomial Fuss–Catalan numbers#✓fully proved

Let \(P\) and \(Q\) be integers with \(\gcd(P, Q) = 1\), let \((U_m)_{m \ge 0}\) be the Lucas sequence of the first kind with parameters \(P\) and \(Q\), and suppose \(U_m \ne 0\) for every \(m \ge 1\). Then for all natural numbers \(r \ge 1\), \(a \ge 2\) and \(n \ge 1\), the rational number

\[\frac{U_r}{U_{(a-1)n+r}} \cdot \frac{\prod_{j=0}^{n-1} U_{an+r-1-j}}{\prod_{j=0}^{n-1} U_{j+1}}\]

is an integer; its second factor is the Lucasnomial coefficient \(\binom{an+r-1}{n}_U\).

theorem generalized_lucasnomial_fuss_catalan_integral_general {P Q : ℤ} {U : ℕ → ℤ}
    (hU : IsLucasSequenceFirstKind P Q U) (hnondeg : ∀ n : ℕ, n ≥ 1 → U n ≠ 0)
    (hreg : Int.gcd P Q = 1) (r a : ℕ) (hr : r ≥ 1) (ha : a ≥ 2) (n : ℕ) (hn : n ≥ 1) :
    ∃ z : ℤ,
      ((U r : ℚ) / ((U ((a - 1) * n + r)) : ℚ)) *
          ((∏ j ∈ Finset.range n, ((U (a * n + r - 1 - j)) : ℚ)) /
            (∏ j ∈ Finset.range n, ((U (j + 1)) : ℚ))) =
        ((z : ℚ))

Uses 4 · Used by 1

Statement usesLucas sequence of the first kind

Proof usesLucas sequence of the first kind: value at one · Lucas sequence of the first kind: value at zero · Lucas sequence of the first kind: the recurrence

Used byGeneralized Lucasnomial Fuss–Catalan numbers are integers (Ballot)

TheoremGeneralized Lucasnomial Fuss–Catalan numbers are integers (Ballot)#✓fully proved

Let \(P\) and \(Q\) be nonzero integers with \(\gcd(P, Q) = 1\), and let \(U : \mathbb{N} \to \mathbb{Z}\) satisfy \(U_0 = 0\), \(U_1 = 1\), \(U_{m+2} = P U_{m+1} - Q U_m\) for every natural number \(m\), and \(U_m \ne 0\) for every \(m \ge 1\). Then for all natural numbers \(r \ge 1\), \(a \ge 2\) and \(n \ge 1\), the rational number

\[\frac{U_r}{U_{(a-1)n+r}} \cdot \frac{\prod_{j=0}^{n-1} U_{an+r-1-j}}{\prod_{j=0}^{n-1} U_{j+1}}\]

is an integer; its second factor is the Lucasnomial coefficient \(\binom{an+r-1}{n}_U\).

theorem generalized_lucasnomial_fuss_catalan_integral (P Q : ℤ)
    (U : ℕ → ℤ) (r a : ℕ) (hP : P ≠ 0) (hQ : Q ≠ 0) (hU0 : U 0 = 0)
    (hU1 : U 1 = 1) (hUrec : ∀ n : ℕ, U (n + 2) = P * U (n + 1) - Q * U n)
    (hnondeg : ∀ n : ℕ, n ≥ 1 → U n ≠ 0) (hreg : Int.gcd P Q = 1)
    (hr : r ≥ 1) (ha : a ≥ 2) (n : ℕ) (hn : n ≥ 1) :
    ∃ z : ℤ,
      ((U r : ℚ) / ((U ((a - 1) * n + r)) : ℚ)) *
          ((∏ j ∈ Finset.range n, ((U (a * n + r - 1 - j)) : ℚ)) /
            (∏ j ∈ Finset.range n, ((U (j + 1)) : ℚ))) =
        ((z : ℚ))

Sources

• Christian Ballot, "Lucasnomial Fuss-Catalan Numbers and Related Divisibility Questions," Journal of Integer Sequences 21 (2018), Article 18.6.5, Theorem thm:2, lines 553–558, https://cs.uwaterloo.ca/journals/JIS/VOL21/Ballot/ballot30.tex. Fundamental Lucas sequences, nondegeneracy, and regularity at lines 185–207; Lucasnomial coefficients at lines 215–221. It follows from generalized_lucasnomial_fuss_catalan_integral_general; the hypotheses hP and hQ are unused and keep the source's shape.

Uses 1

Proof usesIntegrality of generalized Lucasnomial Fuss–Catalan numbers

DefinitionGeneralized Lucasnomial Fuss–Catalan numbers#✓fully proved

Let \(P\) be Lucas parameters, that is, nonzero reals \(p\) and \(q\) whose Lucas bracket sequence \(U_0 = 0\), \(U_1 = 1\), \(U_{m+2} = pU_{m+1} + qU_m\) satisfies \(U_m \ne 0\) for every \(m \ge 1\). Write \(U_m! = U_1 U_2 \cdots U_m\), and let the Lucasnomial coefficient \(\binom{m}{k}_U\) be \(\frac{U_m!}{U_k! \, U_{m-k}!}\) for \(k \le m\) and \(0\) for \(k > m\). For natural numbers \(a\), \(r\) and \(n\), the generalized Lucasnomial Fuss–Catalan number of \(P\) is the real number

\[C_{U,a,r}(n) = \frac{U_r}{U_{(a-1)n+r}} \binom{an+r-1}{n}_U.\]

The source takes \(a \ge 2\), \(r \ge 1\) and \(n \ge 1\). Here \(a\), \(r\) and \(n\) range over all natural numbers: \(a - 1\) and \(an + r - 1\) are truncated at \(0\), and the quotient is \(0\) when \(U_{(a-1)n+r} = 0\).

noncomputable def generalizedLucasnomialFussCatalan
    (P : LucasParameters) (a r n : ℕ) : ℝ :=
  (lucasBracket P r / lucasBracket P ((a - 1) * n + r)) *
    lucasnomial P (a * n + r - 1) n

Sources

• Ballot, JIS Vol. 21.

Uses 3 · Used by 1

Statement usesNondegenerate Lucas parameters · Lucas brackets · Lucasnomial coefficients

Used byThe two indexings of the generalized Lucasnomial Fuss–Catalan numbers agree

DefinitionGeneralized Lucasnomial Fuss–Catalan numbers in the r, s, t notation#✓fully proved

Let \(P\) be Lucas parameters, that is, nonzero reals \(p\) and \(q\) whose Lucas bracket sequence \(U_0 = 0\), \(U_1 = 1\), \(U_{m+2} = pU_{m+1} + qU_m\) satisfies \(U_m \ne 0\) for every \(m \ge 1\). Write \(U_m! = U_1 U_2 \cdots U_m\), and let the Lucasnomial coefficient \(\binom{m}{k}_U\) be \(\frac{U_m!}{U_k! \, U_{m-k}!}\) for \(k \le m\) and \(0\) for \(k > m\). For natural numbers \(r\), \(s\) and \(t\), define the real number

\[C_{U,r,s}(t) = \frac{U_s}{U_{(r-1)t+s}} \binom{rt+s-1}{t}_U.\]

The source takes \(r \ge 2\), \(s \ge 1\) and \(t \ge 1\). Here \(r\), \(s\) and \(t\) range over all natural numbers: \(r - 1\) and \(rt + s - 1\) are truncated at \(0\), and the quotient is \(0\) when \(U_{(r-1)t+s} = 0\).

noncomputable def generalizedLucasnomialFussCatalanRS
    (P : LucasParameters) (r s t : ℕ) : ℝ :=
  (lucasBracket P s / lucasBracket P ((r - 1) * t + s)) *
    lucasnomial P (r * t + s - 1) t

Sources

• Ballot, JIS Vol. 24.

Uses 3 · Used by 1

Statement usesNondegenerate Lucas parameters · Lucas brackets · Lucasnomial coefficients

Used byThe two indexings of the generalized Lucasnomial Fuss–Catalan numbers agree

TheoremThe two indexings of the generalized Lucasnomial Fuss–Catalan numbers agree#✓fully proved

For all Lucas parameters \(P\), with Lucas bracket sequence \(U\), and all natural numbers \(a\), \(r\) and \(n\), the generalized Lucasnomial Fuss–Catalan number \(C_{U,a,r}(n)\) equals \(C'_{U,a,r}(n)\), where \(C'_{U,r,s}(t)\) denotes the generalized Lucasnomial Fuss–Catalan number in the r, s, t notation. The two definitions are the same function.

theorem generalizedLucasnomialFussCatalan_vol24_eq
    (P : LucasParameters) (a r n : ℕ) :
    generalizedLucasnomialFussCatalan P a r n =
      generalizedLucasnomialFussCatalanRS P a r n

Sources

• Ballot, JIS Vol. 21 and Vol. 24.

Uses 3

Statement usesNondegenerate Lucas parameters · Generalized Lucasnomial Fuss–Catalan numbers · Generalized Lucasnomial Fuss–Catalan numbers in the r, s, t notation

5 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.