求通过任意倍数跳转斐波那契索引的通用公式，例：TriplingFunction(Fₙ)=F₃ₙ

Hey there! Great to see you diving deep into Fibonacci number identities—you’ve already covered some really solid ground with Binet’s formula, matrix methods, fast doubling, and polynomial approaches. Let me help you connect the dots on that general index multiplication formula you’re chasing.

The key here is leveraging Fibonacci addition identities and extending them to arbitrary integer multiples. The core identity that unlocks this is the convolution formula for Fibonacci numbers:

Fₘ₊ₙ = Fₘ₊₁Fₙ + FₘFₙ₋₁

Using this, we can recursively build formulas for Fₖₙ where k is any positive integer. Let’s start with your tripling case to make it concrete:

Tripling Example (k=3) #

First, apply the addition identity twice:

1. Let m = 2n, so F₃ₙ = F₂ₙ₊₁Fₙ + F₂ₙFₙ₋₁
2. We already know from doubling identities that:
   • F₂ₙ = Fₙ(2Fₙ₊₁ - Fₙ)
   • F₂ₙ₊₁ = Fₙ₊₁² + Fₙ²

Substitute those into the tripling equation, and you’ll get a simplified polynomial form:
F₃ₙ = 3Fₙ²Fₙ₊₁ - Fₙ³ (or expanded further using Fₙ₊₁ = Fₙ + Fₙ₋₁ if needed)

Extending to Any Integer k #

For any positive integer k, Fₖₙ can be expressed as a polynomial in Fₙ and Fₙ₊₁. This is easiest to visualize using the matrix representation you’re already familiar with:
The Fibonacci transformation matrix is M = [[1, 1], [1, 0]], where Mⁿ = [[Fₙ₊₁, Fₙ], [Fₙ, Fₙ₋₁]]

Raising this matrix to the k-th power gives Mᵏ = [[Fₖ₊₁, Fₖ], [Fₖ, Fₖ₋₁]], and since (Mⁿ)ᵏ = Mᵏⁿ, expanding the right-hand side matrix power lets us extract a closed-form polynomial for Fₖₙ in terms of Fₙ and Fₙ₊₁. This is exactly the generalization of the doubling/tripling functions you’re looking for.

Another compact way to frame this is using Chebyshev polynomials of the second kind—Fibonacci numbers have a direct relationship to these, giving us:
Fₖₙ = Fₙ * Uₖ₋₁(Fₙ₊₁ / Fₙ)
where Uₖ₋₁ is the (k-1)-th Chebyshev polynomial of the second kind. This form condenses the polynomial relationship into a neat, general expression.

If you’ve pored through Ron Knott’s pages, you might have seen specific cases (doubling, tripling) scattered throughout, but this general formula ties all those cases together using matrix exponentiation or Chebyshev polynomial identities.

内容的提问来源于stack exchange，提问作者iambryanhaney