Z会の今まで見たこともない漸化式からある不思議な関連を発見

質問

とても不思議と僕は思っておりますので、ちょっと長くなりますが、どうかお付き合いください。
Z会の問題をヒントに、次のことを発見しました。

a[1]=1 , a[2]=4
a[n+2] - 3a[n+1] + a[n] = 0
⇔
a[n]<a[n+1] , a[1]=1
a[n+1]^2 - 3a[n]a[n+1] + a[n]^2 = 5

という、漸化式の不思議な同値性です。
ちなみに、{a[n]}={1,4,11,29,76,199,521,…}

(⇒)を示すのは比較的簡単です。見通しよくするために構成的に証明してみます。
t^2-3t+1=0の解をα,βとすると、α+β=3,αβ=1
a[n+2] - αa[n+1] = β(a[n+1] - αa[n])
よって、
a[n+1] - αa[n] = β^(n-1) (4 - α)
同様に、
a[n+1] - βa[n] = α^(n-1) (4 - β)
これらをかけて、整理すると、
a[n+1]^2 - 3a[n]a[n+1] + a[n]^2 = 5
また、a[n]<a[n+1]は数学的帰納法で示すことが出来ます。

しかし、反対方向の証明がわかりません。
数列の正体は、
a[n]={(1+√5)/2}{(3+√5)/2}^(n-1) + {(1-√5)/2}{(3-√5)/2}^(n-1)
なので、それを仲介して大量の計算をすれば証明できるかもしれませんが、見通しよくありません。
a[n+2] - 3a[n+1] + a[n] = 0　という漸化式の解空間は、2次元線形空間になります。つまり、二つの解の和も解だし、一つの解の実数倍も解だし、第一項と第二項が定まれば全部の項が定まるので2次元です。

a[1]=1 , a[n+1]^2 - 3a[n]a[n+1] + a[n]^2 = 5
という2項間漸化式は、 a[n]の値からa[n+1]の値を求めるとき、2つに分岐しますが、それを適当に定めることによって、3項間線形漸化式に帰着されるのはなぜでしょうか？
どのような構造があるのでしょうか?

http://oshiete1.goo.ne.jp/qa4936699.html
で質問させていただいたことと関連して、背景が気になります。

回答No.1

stomachman

> 反対方向の証明
添え字をひとつずらしてみれば、
a[n+1]^2 - 3a[n]a[n+1] + a[n]^2 = a[n+2]^2 - 3a[n+1]a[n+2] + a[n+1]^2,
これを
(-a[n+2] + 3a[n+1])a[n+2] +(- 3a[n+1] + a[n])a[n] = 0.
と整理しておいて、
U[n] = a[n+2] - 3a[n+1] + a[n]
とおけば
(a[n]-U[n])a[n+2] +(U[n]-a[n+2])a[n] = 0,
なので
U[n](a[n]-a[n+2])=0.
でも
a[n+2]＞a[n]
だから
U[n]=0.
あとは数列aの一意性を言えば十分？

お礼

まことにありがとうございます。

Z会の本来の問題は次のような形でした。
a[1]=1 , a[2]=4 , a[n+2]=3a[n+1] - a[n] とする。
(1)a[n+1]^2 - 5 = a[n+2]a[n] を示せ。
(2)x^2をyで割ると5余り、y^2をxで割ると5余る3ケタのx,yの組を一つ求めよ。

この問題を元に、いろいろな疑問が思い浮かんできています。
題意の漸化式を行列で表現すると、
((a[n+2] a[n+1]) (a[n+1] a[n])) = ((3 -1) (1 0)) * ((a[n+1] a[n]) (a[n] a[n-1]))
これを繰り返し用いると、
((a[n+1] a[n]) (a[n] a[n-1])) = ((3 -1) (1 0))^n * ((11 4) (4 1))
この両辺の行列式を取ったものが(1)の漸化式になります。

逆に、(1)の漸化式 a[n+1]^2 - 5 = a[n+2]a[n] で、初項と第二項a[1]=1 , a[2]=4 を与えると、元の数列が復元されるわけですが、これを、行列 (a[n+2] a[n+1]) (a[n+1] a[n])) の言葉を使って書くと、行列の初項が、 (a[3] a[2]) (a[2] a[1]))=((11 4) (4 1)) で、行列式が常に -5 であれば、
((a[n+2] a[n+1]) (a[n+1] a[n])) = ((3 -1) (1 0)) * ((a[n+1] a[n]) (a[n] a[n-1]))
ということです。これを行列の性質を使ってエレガントに示したいと思っているのですが。

(1)の漸化式 a[n+1]^2 - 5 = a[n+2]a[n] に、題意の a[n+2]=3a[n+1] - a[n] を代入すると、質問文で書いた a[n+1]^2 - 3a[n]a[n+1] + a[n]^2 = 5 が得られます。
(x,y)=(a[n],a[n+1])とすると、y^2-3xy+x^2=5 という二次曲線になります。今、数列a[n]は整数列なので、二次曲線上の格子点の一部が求められたことになります。
では、逆に、y^2-3xy+x^2=5 という二次曲線上の格子点を求める問題として出発すると、どのようにして解かれるのでしょうか?

(2)の問題を解くには、上記の二次曲線上の格子点を(x,y)としてとればいいわけですが、逆に、
x^2≡5 (mod y)
y^2≡5 (mod x)
を求める問題として出発すると、どのようにして解かれるのでしょうか?

漸化式、行列、二次曲線の格子点、連立合同式の関係を上手に整理したいと思って考えているのですが。