Cassiniの恒等式(Cassini's identity)とは、Fibonacci 数 $F_n$ について、すべての $n\ge1$ で $F_{n+1}F_{n-1}-F_n^2=(-1)^n$ が成り立つという恒等式である。行列 $\begin{pmatrix}1&1\\1&0\end{pmatrix}$ の $n$ 乗の行列式を計算したものにあたる。隣り合う項が互いに素であること、比 $F_{n+1}/F_n$ が黄金比の上下に交互にきて収束することが従い、逆に $x^2-xy-y^2=\pm1$ の正の整数解は隣り合う Fibonacci 数の組に限る。切り貼りで面積が $1$ 変わって見えるパズルの説明も与える。
前提知識: Fibonacci数, 行列式, 数学的帰納法
Fibonacci数 $0,1,1,2,3,5,8,13,21,\dots$ の続いた 3 項をとり、両端の積と中央の平方を比べると、差がいつも $\pm1$ になる。$5\cdot13=65$ と $8^2=64$、$8\cdot21=168$ と $13^2=169$ のように、$+1$ と $-1$ が交互に現れる。これが Cassiniの恒等式(Cassini's identity)である。
式 1 本の小さな事実だが、Fibonacci 数の行列表示の行列式そのものであり、隣り合う項が互いに素であること、比 $F_{n+1}/F_n$ が黄金比の上下に交互にくること、Fibonacci 数の判定法、そして 64 と 65 が等しく見える図形のパズルの説明を与える。
| 問い | 答え |
|---|---|
| 何を言うのか | $F_{n+1}F_{n-1}-F_n^2=(-1)^n$(thm-cas-main) |
| なぜ成り立つか | 行列 $\begin{pmatrix}1&1\\1&0\end{pmatrix}$ の行列式が $-1$ だから |
| 初期値を変えると | 右辺に定数が付く(prop-cas-general) |
| 一般化は | 添字を離した形が成り立つ(prop-cas-ocagne、prop-cas-four) |
| 逆は | $x^2-xy-y^2=\pm1$ の正の整数解は隣り合う項に限る(thm-cas-converse) |
$F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$($n\ge0$)で第 $n$ Fibonacci 数 $F_n$ を定める。
すべての $n\ge1$ について
$$
F_{n+1}F_{n-1}-F_n^2=(-1)^n
$$
である。
行列式による証明:$Q=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ とおく。$n\ge1$ について
$$
Q^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}
$$
である。実際、$n=1$ では $F_2=F_1=1$、$F_0=0$ なので正しく、$n$ で正しければ
$$
Q^{n+1}=Q^nQ=\begin{pmatrix}F_{n+1}+F_n&F_{n+1}\\F_n+F_{n-1}&F_n\end{pmatrix}=\begin{pmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_n\end{pmatrix}
$$
である。行列式 は積を保つので $\det(Q^n)=(\det Q)^n=(-1)^n$ であり、左辺は上の表示から $F_{n+1}F_{n-1}-F_n^2$ である。$\square$
| $n$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
|---|---|---|---|---|---|---|---|---|
| $F_{n+1}F_{n-1}$ | $0$ | $2$ | $3$ | $10$ | $24$ | $65$ | $168$ | $442$ |
| $F_n^2$ | $1$ | $1$ | $4$ | $9$ | $25$ | $64$ | $169$ | $441$ |
| 差 | $-1$ | $1$ | $-1$ | $1$ | $-1$ | $1$ | $-1$ | $1$ |
$F_{n-1}=F_{n+1}-F_n$ を代入すると、同じことを 2 項だけで書ける。
すべての $n\ge1$ について $F_{n+1}^2-F_{n+1}F_n-F_n^2=(-1)^n$ である。
$F_{n+1}F_{n-1}=F_{n+1}(F_{n+1}-F_n)$ を thm-cas-main に代入すればよい。$\square$
Hardy–Wright はこの恒等式を $u_n^2-u_{n-1}u_{n+1}=(-1)^{n-1}$ の形で挙げている(HW60 §10.14、(10.14.8)、p. 149)。また Dickson の歴史書は、続いた 3 項について中央の平方と両端の積の差が $\pm1$ であることを R. Simson(1753 年)の記述として挙げている(Dic05 p. 393)。
帰納法による thm-cas-main の証明:$C_n:=F_{n+1}F_{n-1}-F_n^2$ とおく。$C_1=F_2F_0-F_1^2=-1$ である。$n\ge1$ のとき
$$
C_{n+1}=F_{n+2}F_n-F_{n+1}^2=(F_{n+1}+F_n)F_n-F_{n+1}(F_n+F_{n-1})=F_n^2-F_{n+1}F_{n-1}=-C_n
$$
なので、$C_n=(-1)^{n-1}C_1=(-1)^n$ である。$\square$
この証明で使ったのは漸化式だけである。したがって初期値を変えても同じ計算が通る(prop-cas-general)。
一般項による thm-cas-main の証明:$\varphi=\frac{1+\sqrt5}2$、$\psi=\frac{1-\sqrt5}2$ とすると $\varphi\psi=-1$、$(\varphi-\psi)^2=5$ であり、Binetの公式(Fibonacci数) より $F_n=(\varphi^n-\psi^n)/\sqrt5$ である。展開すると $\varphi^{2n}$ と $\psi^{2n}$ の項は打ち消し合い、
$$
5(F_{n+1}F_{n-1}-F_n^2)=2(\varphi\psi)^n-\varphi^{n+1}\psi^{n-1}-\varphi^{n-1}\psi^{n+1}=-(\varphi\psi)^{n-1}(\varphi-\psi)^2
$$
となる。右辺は $-5(-1)^{n-1}=5(-1)^n$ である。$\square$
敷き詰めの数え上げでは、$F_{m+1}$ が長さ $m$ の帯を長さ $1$ と $2$ のタイルで敷く方法の数であることを使う(Fibonacci数の母関数 の命題「1 と 2 の順序付きの和の数」)。恒等式は、ほとんどの組を一対一に対応させると、余りが 1 組だけ残るという形で読める。
敷き詰めによる thm-cas-main の証明。要点:長さの違う帯を 1 マスずらして重ね、2 本に共通の切れ目で尾を交換する。切れ目のない組が 1 組だけ残り、それが右辺の $\pm1$ になる。
$n\ge1$ とし、長さ $m$ の帯の敷き方の数を $f_m=F_{m+1}$ とする($f_0=1$)。マス $1,\dots,n+1$ の直線の上に 2 本の帯を上下に置く。組 (A) は、上の帯がマス $1,\dots,n$、下の帯がマス $2,\dots,n+1$ を占める組で、全部で $f_n^2$ 組ある。組 (B) は、上の帯がマス $1,\dots,n+1$、下の帯がマス $2,\dots,n$ を占める組で、全部で $f_{n+1}f_{n-1}$ 組ある。
マス $k$ と $k+1$ の境目($1\le k\le n$)で、上の帯も下の帯もタイルの切れ目をもつとき(帯の端も切れ目と数える)、この境目を共通の切れ目と呼ぶ。共通の切れ目をもつ組について、最後の共通の切れ目より右の部分を上下で入れかえる。すると (A) の組は (B) の組に、(B) の組は (A) の組になる。共通の切れ目の位置は変わらないので、もう 1 回同じ操作をすると元に戻る。よって、共通の切れ目をもつ (A) の組と (B) の組は同数である。
共通の切れ目をもたない組を調べる。どちらの場合も、下の帯はマス $2$ から始まるので境目 $1$ は下の帯の切れ目である。よって上の帯の最初のタイルはマス $1,2$ を覆う長さ $2$ のタイルである。すると境目 $2$ は上の帯の切れ目なので、下の帯の最初のタイルはマス $2,3$ を覆う長さ $2$ のタイルである。これを続けると、2 本の帯はどちらも長さ $2$ のタイルだけからなる。(A) でこれができるのは $n$ が偶数のときだけで、そのときちょうど 1 組ある。(B) でこれができるのは $n$ が奇数のときだけで、そのときちょうど 1 組ある。
以上から $f_n^2-f_{n+1}f_{n-1}=(-1)^n$、すなわち $F_{n+1}^2-F_{n+2}F_n=(-1)^n$ である。$n+1$ を $n$ に置きかえると $n\ge2$ の主張になり、$n=1$ は直接確かめられる。$\square$
prf-cas-induction は初期値を使っていないので、次の形になる。
実数列 $(a_n)_{n\ge0}$ が $a_{n+2}=a_{n+1}+a_n$ を満たすとする。$c:=a_1^2-a_2a_0$ とおくと、すべての $n\ge1$ について
$$
a_{n+1}a_{n-1}-a_n^2=(-1)^nc
$$
である。
$C_n:=a_{n+1}a_{n-1}-a_n^2$ とおくと、prf-cas-induction と同じ計算で $C_{n+1}=-C_n$ である。$C_1=a_2a_0-a_1^2=-c$ なので $C_n=(-1)^{n-1}C_1=(-1)^nc$ である。$\square$
$F_n$ では $c=1$ である。
Lucas 数 $L_0=2$、$L_1=1$、$L_{n+2}=L_{n+1}+L_n$($2,1,3,4,7,11,\dots$)は同じ漸化式を満たすが、$c=1-3\cdot2=-5$ である。したがって $L_{n+1}L_{n-1}-L_n^2=5(-1)^{n+1}$ で、たとえば $L_3L_1-L_2^2=4-9=-5$ である(HW60 (10.14.9)、p. 149)。右辺が $\pm1$ であるのは、漸化式だけでなく初期値 $F_0=0$、$F_1=1$ による。
$a_0=0$、$a_1=1$、$a_{n+2}=a_{n+1}+2a_n$($0,1,1,3,5,11,21,\dots$)では、$a_2a_0-a_1^2=-1$、$a_3a_1-a_2^2=2$、$a_4a_2-a_3^2=-4$、$a_5a_3-a_4^2=8$ である。初期値は同じでも、行列 $\begin{pmatrix}1&2\\1&0\end{pmatrix}$ の行列式が $-2$ なので、右辺は $\pm1$ でなく $\pm2^{n-1}$ になる。一般の 2 項の線形漸化式については Lucas数列の関係式 の命題「行列表示」を見よ。
Cassini の恒等式の行列式は、隣り合う 2 本の列ベクトルの行列式である。離れた 2 本でも同じことができる。
$m\ge n\ge0$ のとき
$$
F_mF_{n+1}-F_{m+1}F_n=(-1)^nF_{m-n}
$$
である。
$v_k:=\begin{pmatrix}F_{k+1}\\F_k\end{pmatrix}$ とおくと $Qv_k=v_{k+1}$ である。2 本の列ベクトルを並べた行列を $[v_a,v_b]$ と書くと、$Q^n[v_{m-n},v_0]=[v_m,v_n]$ である。$\det[v_{m-n},v_0]=F_{m-n+1}\cdot0-1\cdot F_{m-n}=-F_{m-n}$、$\det Q^n=(-1)^n$ なので
$$
F_{m+1}F_n-F_mF_{n+1}=\det[v_m,v_n]=(-1)^{n+1}F_{m-n}
$$
である。$\square$
$m=n+1$ とすると $F_{n+1}^2-F_{n+2}F_n=(-1)^n$ となり、これは $n+1$ についての Cassini の恒等式である。M. d'Ocagne は 1885–86 年の論文でこの形の式を証明している(Dic05 p. 402 の $u_pu_i-u_{p+1}u_{i-1}=(-1)^{i+1}u_{p-i+1}$ で、$p=m$、$i=n+1$ に当たる)。
$n,i,j\ge0$ のとき
$$
F_{n+i}F_{n+j}-F_nF_{n+i+j}=(-1)^nF_iF_j
$$
である。
$i=0$ なら両辺とも $0$ である。$i\ge1$ とする。加法定理 $F_{k+i}=F_iF_{k+1}+F_{i-1}F_k$($k\ge0$)を $k=n$ と $k=n+j$ に使う(加法定理は $Q^{k+i}=Q^kQ^i$ の成分の比較で得られる。$k=0$ は $F_i=F_i$ である)と、
$$
F_{n+i}F_{n+j}-F_nF_{n+i+j}=(F_iF_{n+1}+F_{i-1}F_n)F_{n+j}-F_n(F_iF_{n+j+1}+F_{i-1}F_{n+j})=F_i\bigl(F_{n+j}F_{n+1}-F_{n+j+1}F_n\bigr)
$$
である。括弧の中は prop-cas-ocagne を $m=n+j$ に使うと $(-1)^nF_j$ である。$\square$
$n\ge r\ge0$ のとき $F_n^2-F_{n-r}F_{n+r}=(-1)^{n-r}F_r^2$ である。
prop-cas-four の $n$ を $n-r$ とし、$i=j=r$ とする。$\square$
$r=1$ とすると Cassini の恒等式である。たとえば $n=7$、$r=3$ で $169-3\cdot55=4=F_3^2$ である。E. Catalan がこの形を証明したことは Dic05 p. 402 に(同書の添字は $1$ ずれている)、初期値を一般にした prop-cas-four の形の式が A. Tagiuri にあることは同 p. 404 にある。Lucas数列の関係式 の節「Cassini型・Catalan型恒等式」には、一般の Lucas 数列での添字が等間隔の形がある。
cor-cas-two-terms の逆が成り立つ。Fibonacci 数の隣り合う組は、この不定方程式の正の整数解をちょうど尽くす。
正の整数の組 $(x,y)$ について、$x^2-xy-y^2=\pm1$ であるのは、ある $n\ge1$ について $(x,y)=(F_{n+1},F_n)$ のとき、かつそのときに限る。
十分性は cor-cas-two-terms である。必要性を $x+y$ についての帰納法で示す。$x^2-xy-y^2=\pm1$ とする。
$x< y$ とすると $y\ge2$ で、$x^2-xy-y^2=x(x-y)-y^2\le-x-y^2\le-5$ となり矛盾する。よって $x\ge y$ である。$x=y$ なら $-x^2=\pm1$ から $x=y=1$ で、$(x,y)=(F_2,F_1)$ である。
$x>y$ とする。$(x',y'):=(y,x-y)$ は正の整数の組で、$x'+y'=x< x+y$ であり、
$$
x'^2-x'y'-y'^2=y^2-y(x-y)-(x-y)^2=-(x^2-xy-y^2)=\mp1
$$
である。帰納法の仮定から $(y,x-y)=(F_{n+1},F_n)$($n\ge1$)と書ける。すると $x=F_{n+1}+F_n=F_{n+2}$、$y=F_{n+1}$ である。$\square$
証明は、$(x,y)$ から $(y,x-y)$ へ進むことで、値の符号を変えながら組を小さくしている。これは漸化式を逆にたどることであり、Euclidの互除法 の引き算の形でもある。
$1\le x,y\le1981$ の範囲で $(x^2-xy-y^2)^2=1$ を満たす組のうち $x+y$ が最大のものは、thm-cas-converse により隣り合う Fibonacci 数の組である。$F_{17}=1597$、$F_{18}=2584$ なので、答えは $(x,y)=(1597,987)$ である。$x^2+y^2$ の最大値も同じ組で与えられ、$3524578$ である。
正の整数 $N$ について、次は同値である。
整数 $x,y$ について $(2x-y)^2-5y^2=4(x^2-xy-y^2)$ である。
1 ならば 2:$N=F_n$($n\ge1$)とし、$x=F_{n+1}$、$y=N$、$m=2x-y$ とおくと、cor-cas-two-terms により $m^2-5N^2=\pm4$ である。
2 ならば 1:$m\ge0$ で $m^2=5N^2\pm4$ とする。$5N^2\pm4=0$ とはならないので $m\ge1$ である。$m^2\equiv5N^2\equiv N^2\pmod2$ なので $m$ と $N$ の偶奇は同じであり、$x:=(m+N)/2$ は正の整数である。$y:=N$ とおくと $2x-y=m$ だから $x^2-xy-y^2=(m^2-5N^2)/4=\pm1$ である。thm-cas-converse により $N=y$ は Fibonacci 数である。$\square$
たとえば $N=89$ では $5N^2-4=39601=199^2$ である。$N=100$ では $5N^2\pm4$ は $50004$ と $49996$ で、$223^2=49729$、$224^2=50176$ の間にあるのでどちらも平方数でなく、$100$ は Fibonacci 数でない。thm-cas-converse の必要性の向きと cor-cas-test の 2 ならば 1 は、J. Wasteels に帰されている(Dic05 p. 405)。
すべての $n\ge0$ について $F_n$ と $F_{n+1}$ は 互いに素 である。
$n=0$ では $\gcd(0,1)=1$ である。$n\ge1$ なら、$F_n$ と $F_{n+1}$ の公約数は thm-cas-main の左辺を割り切るので $1$ を割り切る。$\square$
$F_n$ の比を $a_n:=F_{n+1}/F_n$($n\ge1$)とおく。thm-cas-main を $F_nF_{n-1}$ で割ると、$n\ge2$ で
$$
a_n-a_{n-1}=\frac{F_{n+1}F_{n-1}-F_n^2}{F_nF_{n-1}}=\frac{(-1)^n}{F_nF_{n-1}}
$$
である。隣り合う比の差が $\pm1$ を分子にもつ分数になるのは、$a_n$ が 黄金比 の連分数の収束子だからである。
数列 $(a_{2k+1})_{k\ge0}$ は狭義単調増加、$(a_{2k})_{k\ge1}$ は狭義単調減少で、どちらも黄金比 $\varphi=\frac{1+\sqrt5}2$ に収束する。
上の式を 2 回使うと、$n\ge2$ で
$$
a_{n+1}-a_{n-1}=(-1)^n\Bigl(\frac1{F_nF_{n-1}}-\frac1{F_{n+1}F_n}\Bigr)=\frac{(-1)^n(F_{n+1}-F_{n-1})}{F_{n-1}F_nF_{n+1}}=\frac{(-1)^n}{F_{n-1}F_{n+1}}
$$
である。よって $n$ が奇数なら $a_{n+1}< a_{n-1}$、偶数なら $a_{n+1}>a_{n-1}$ である。また $a_{2k}-a_{2k-1}=\dfrac1{F_{2k}F_{2k-1}}>0$ であり、これは $k\to\infty$ で $0$ に近づく。したがって奇数番目の列は増加、偶数番目の列は減少で、奇数番目の項は偶数番目の項より小さく、差は $0$ に近づく。よって 2 つの列は共通の極限 $a>0$ をもつ。$a_n=1+F_{n-1}/F_n=1+1/a_{n-1}$($n\ge2$)で $n\to\infty$ とすると $a=1+1/a$ である。$a>0$ なので $a=\varphi$ である。$\square$
この証明は一般項の公式を使わず、極限の存在も示している。同じ極限を一般項の公式から導く証明は Fibonacci数 の命題「隣り合う項の比の極限」にある。
$\mathbb{Z}[\varphi]$ の元 $a+b\varphi$ のノルムは $N(a+b\varphi)=(a+b\varphi)(a+b\psi)=a^2+ab-b^2$ である。$\varphi^n=F_n\varphi+F_{n-1}$(黄金比 の命題「黄金比の基本的な等式」)と $N(\varphi)=\varphi\psi=-1$ から、$F_{n-1}^2+F_{n-1}F_n-F_n^2=(-1)^n$ が得られる。これは Cassini の恒等式の 1 つの形であり、$\varphi^n$ が単数であることを言っている(2次体 の $d=5$ の例)。thm-cas-converse は、$\mathbb{Z}[\varphi]$ の単数が $\pm\varphi^n$($n\in\mathbb{Z}$)に限ることに対応する初等的な事実である。
Fibonacci 数は、面積が変わって見える図形のパズルの種にもなる(このつながりを示した E. B. Escott の記事が Dic05 p. 405 に挙げられている)。
一辺 $8$ の正方形を、幅 $3$ の帯と幅 $5$ の帯に分ける(下の図 1 の左)。幅 $3$ の帯は対角線で 2 つの直角三角形(直角をはさむ 2 辺が $3,8$)に、幅 $5$ の帯は 2 つの台形(平行な 2 辺が $3,5$、高さ $5$)に切る。この 4 枚を並べ直すと、見かけの上では $5\times13$ の長方形になる。
面積は $64$ から $65$ に増えて見えるが、切り貼りで面積は変わらない。「4 枚が長方形を隙間なく埋める」という見かけの主張が正しくない。長方形の対角線に見える線は 1 本の直線でなく、三角形の斜辺(傾き $3/8$)と台形の斜辺(傾き $2/5$)がつながったものである。図 1 の右のように左下の角を原点にとると、$(0,0)$、$(8,3)$、$(13,5)$、$(5,2)$ を頂点とする平行四辺形の隙間が残り、その面積は $|8\cdot2-3\cdot5|=1$ である。ちょうど差の $65-64$ を埋めている。
左は一辺 8 の正方形を 2 つの三角形と 2 つの台形に切ったもの。右は同じ 4 枚を 5 かける 13 の長方形の形に並べたもので、対角線に沿って赤い細い平行四辺形の隙間が残る
一般に、$n\ge4$ のとき一辺 $F_n$ の正方形を、幅 $F_{n-2}$ と幅 $F_{n-1}$ の帯に分けて同じように切ると、見かけの上では $F_{n+1}\times F_{n-1}$ の長方形になる。Cassini の恒等式により、面積の差は $\pm1$ である。$n$ が偶数なら隙間ができて長方形の方が大きく見え、$n$ が奇数なら 4 枚が細い平行四辺形の分だけ重なって小さく見える。$n$ が大きいほど $F_{n+1}/F_n$ と $F_n/F_{n-1}$ の差は小さく、隙間は細くなって見分けにくい。隙間の平行四辺形の面積は $|F_nF_{n-3}-F_{n-2}F_{n-1}|$ で、prop-cas-four により $n$ によらず $1$ のままである。
漸化式 $F_{n+2}=F_{n+1}+F_n$ で添字を負の方へ伸ばすと $F_{-n}=(-1)^{n+1}F_n$ となる(HW60 (10.14.5)、p. 148)。$Q$ は可逆なので、行列表示はすべての整数 $n$ で成り立ち、thm-cas-main もすべての整数 $n$ で成り立つ。$n=0$ なら $F_1F_{-1}-F_0^2=1$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する