文献あり

Fibonacci trace formula

Here's an observation I posted on Twitter together with a proof .
The Twitter version has some errors which I have fixed, but further corrections are welcome!

Let $M$ be an integer $k \times k$ matrix with distinct eigenvalues $a_{1}, \dots, a_{k}$ , and characteristic polynomial $P (x) = (x - a_{1}) \dots (x - a_{k}) = x^{k} - \sum_{i = 0}^{k - 1} b_{i} x^{i}$ .
Then the equation $f_{n} := trace (M^{n} \cdot {P^{'} (M)}^{- 1}) (n = 0, 1, 2, \dots)$ defines a sequence of integers.

You can recover the Multinacci numbers (ｋ−ナッチ数) by plugging in a companion matrix for $M$ .

For instance if you choose $M = (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})$ , then
$P (x) = x^{2} - x - 1 = (x - \frac{1 + \sqrt{5}}{2}) (x - \frac{1 - \sqrt{5}}{2})$ and $P^{'} (M) = 2 M - I = (\begin{matrix} - 1 & 2 \\ 2 & 1 \end{matrix})$ .
The $f_{n}$ turn out to be the Fibonacci numbers, but ${P^{'} (M)}^{- 1} = \frac{1}{5} (\begin{matrix} - 1 & 2 \\ 2 & 1 \end{matrix})$ is not an integer matrix.
It is not obvious why the trace should be an integer in general.

The first $k$ values are $f_{0} = \dots = f_{k - 2} = 0$ and $f_{k - 1} = 1$ .

The proof idea is thanks to @apu_yokai, who linked to his older article about partial fraction decomposition.

As $M$ has $k$ distinct eigenvalues $a_{1}, . . ., a_{k}$ we can act (for the purpose of computing the trace) as if $M$ were diagonal:
$f_{n} = \sum_{i = 1}^{k} \frac{a_{i}^{n}}{P^{'} (a_{i})} (n = 0, 1, 2, \dots)$

By partial fraction decomposition we get $f_{0}$ :

$\sum_{i = 1}^{k} \frac{x}{x - a_{i}} \frac{1}{P^{'} (a_{i})} = \frac{x}{(x - a_{1}) \dots (x - a_{k})} = \frac{x}{P (x)}$

Take the limit $x \to \infty$ :

$f_{0} = \sum_{i = 1}^{k} \frac{1}{P^{'} (a_{i})} = {\begin{cases} 0 & for 1 < k \\ 1 & for 1 = k \end{cases}$

$f_{1}, . . ., f_{k - 1}$ we get inductively.
$n - 1 \to n$ , while $n < k$ :

$\underset{= 0}{\underset{⏟}{(x^{n - 1} f_{0} + x^{n - 2} f_{1} + . . . + x f_{n - 2} + f_{n - 1}) x}} + \sum_{i = 1}^{k} \frac{a_{i}^{n} x}{x - a_{i}} \frac{1}{P^{'} (a_{i})}$

$= \sum_{i = 1}^{k} ((x^{n - 1} + x^{n - 2} a_{i} + . . . + x a_{i}^{n - 2} + a_{i}^{n - 1}) x + \frac{a_{i}^{n} x}{x - a_{i}}) \frac{1}{P^{'} (a_{i})}$

$= \sum_{i = 1}^{k} \frac{(x^{n} - a_{i}^{n}) x + a_{i}^{n} x}{x - a_{i}} \frac{1}{\prod_{j \neq i} (a_{i} - a_{j})} = \frac{x^{n + 1}}{P (x)}$

Therefore

$f_{n} = lim_{x \to \infty} \sum_{i = 1}^{k} \frac{a_{i}^{n} x}{x - a_{i}} \frac{1}{P^{'} (a_{i})} = lim_{x \to \infty} \frac{x^{n + 1}}{P (x)} = {\begin{cases} 0 & if n < k - 1 \\ 1 & if n = k - 1 \end{cases}$

The sequence ${(f_{n})}_{n \geq 0}$ satisfies the recursion scheme $f_{n + k} = \sum_{i = 0}^{k - 1} b_{i} f_{n + i}$ for all $n \geq 0$ .

This is due to Cayley-Hamilton and linearity of the trace

$\begin{aligned} M^{n} P (M) P^{'} (M)^{- 1} = 0 \\ ⟹ & M^{n + k} P^{'} (M)^{- 1} = \sum_{i = 0}^{k - 1} b_{i} M^{n + i} P^{'} (M)^{- 1} \\ ⟹ & trace (M^{n + k} P^{'} (M)^{- 1}) = \sum_{i = 0}^{k - 1} b_{i} trace (M^{n + i} P^{'} (M)^{- 1}) \\ ⟺ & f_{n + k} = \sum_{i = 0}^{k - 1} b_{i} f_{n + i} \end{aligned}$

Because the initial values are integers and above recursion scheme has integer coefficients all $f_{n}$ are integers.

Fibonacci trace formula

The condition that $M$ has distinct eigenvalues means that $gcd (P, P^{'}) = 1$ , so $P^{'} (M)$ is invertible, and the sequence is well-defined.
Via Lemma 2 the sequence satisfies a recursion scheme with integral coefficients $b_{i}$ , and the initial values are also integral by Lemma 1. Therefore all $f_{n}$ are integral by induction.