n個の数 a[1]、…、a[n] に対して p[i]、q[i] (i=0、1、…、n) を次のように定める。
p[0]=1
p[1]=a[1]
p[i]=a[i]*p[i-1]+p[i-2] (i=2、…、n)
q[0]=1
q[1]=a[n]
q[i]=a[n-i+1]*q[i-1]+q[i-2] (i=2、…、n)
このとき、 p[n]=q[n] となることを示せ。
また、 p[i]*q[n-i]+p[i-1]*q[n-i-1]=p[n]=q[n] (i=1、…、n-1) となることを示せ。
（コメント） ｎ＝３のときの様子を観察すると、
p[0]=1
p[1]=a[1]
p[2]=a[2]*p[1]+p[0]=a[2]*a[1]+1
p[3]=a[3]*p[2]+p[1]=a[3]*(a[2]*a[1]+1)+a[1]=a[3]*a[2]*a[1]+a[3]+a[1]
q[0]=1
q[1]=a[3]
q[2]=a[2]*q[1]+q[0] =a[2]*a[3]+1
q[3]=a[1]*q[2]+q[1] =a[1]*(a[2]*a[3]+1)+a[3]=a[1]*a[2]*a[3]+a[1]+a[3]
確かに、 p[3]=q[3] ですね！
DD++さんからのコメントです。（令和２年８月１６日付け）
p[n]
= a[n]*p[n-1] + 1*p[n-2]
= q[1]*p[n-1] + q[0]*p[n-2]
= q[1]*(a[n-1]*p[n-2]+p[n-3]) + q[0]*p[n-2]
= (a[n-1]*q[1]+q[0])*p[n-2] + q[1]*p[n-3]
= q[2]*p[n-2] + q[1]*p[n-3]
= q[2]*(a[n-2]*p[n-3]+p[n-4]) + q[1]*p[n-3]
= (a[n-2]*q[2]+q[1])*p[n-3] + q[2]*p[n-4]
= q[3]*p[n-3] + q[2]*p[n-4]
（同様に繰り返し）
= q[n-2]*p[2] + q[n-3]*p[1]
= q[n-2]*(a[2]*p[1]+p[0]) + q[n-3]*p[1]
= (a[2]*q[n-2]+q[n-3])*p[1] + q[n-2]*p[0]
= q[n-1]*p[1] + q[n-2]*p[0]
= q[n-1]*a[1] + q[n-2]*1
= q[n]
証明終。
……というだけでは、りらひいさんの意図したもの全く拾えていないと思うので、以下に少し
実験。
n=6, {a[n]} = 1,1/2,1/3,1/4,1/5,1/6 の場合
{p[n]} = 1,3/2,3/2,15/8,15/8,35/16 （p[0]は省略）
これに対し、
b[i] = 1/(a[i]*a[i+1]) (1≦i≦5)
r[i] = p[i]/(a[1]*a[2]*...*a[i]) (1≦i≦6)
とすると、
{b[n]} = 2,6,12,20,30
{r[n]} = 1,3,9,45,225,1575
この {r[n]} ですが、数列 {b[n]} の隣接しない何項かを選択して積をとる（何も選択しなかった
場合、積は1とする）全パターンの総和になっています。
r[1] = 1
r[2] = 1 + 2 = 3
r[3] = 1 + 2 + 6 = 9
r[4] = 1 + 2 + 6 + 12 + 2*12 = 45
r[5] = 1 + 2 + 6 + 12 + 20 + 2*12 + 2*20 + 6*20 = 225
r[6] = 1 + 2 + 6 + 12 + 20 + 30 + 2*12 + 2*20 + 2*30 + 6*20 + 6*30 + 12*30 + 2*12*30 = 1575
この性質は、 r[1] = p[1]/a[1] = 1 であることと、
p[i] = a[i]*p[i-1] + p[i-2] の両辺を (a[1]*a[2]*...*a[i]) で割ることで r[i] = r[i-1] + b[i-1]*r[i-2]
という漸化式が得られることにより示されます。
一方、{q[n]} は {a[n]} を逆順にして同様の操作をすることを意味しています。
上の数列の例に対しては、
{a’[n]} = 1/6,1/5,1/4,1/3,1/2,1
{q[n]} = 1/6,31/30,51/120,141/120,81/80,35/16
{b’[n]} = 30,20,12,6,2
{r’[n]} = 1,31,51,423,729,1575
となりますが、上の法則を考えれば、 r[6] と r’[6] は同じ内容の積の総和になるため一致
することは明らかで、元に戻せば p[6] = q[6] となるのも自明ということになります。
さて、これを見ると、隣接しないものを選び出して演算するところに「ゼッケンドルフの定理」
の面影を感じますが……さすがに関係なさそうかなあ。うーん、背景にあるものはなんだろう？
りらひいさんからのコメントです。（令和２年８月１６日付け）
……というだけでは、りらひいさんの意図したもの全く拾えていないと思うので、以下に少し
実験。
わたしが意図したところは、変なところから問題を作ったので普通に解けるのか気になった
というだけです。素直に式変形だけでいけると分かっただけでも十分です。というか、わたし
が式変形をろくに試してもいなかったのがよくなかったのですが……。
うーん、背景にあるものはなんだろう？
そんなに大層な背景はありません。もともとは2次正方行列でした。
A[i]={{0,1},{1,a[i]}} とおくと、A[1]…A[i] の(2,1)成分がp[i-1]、(2,2)成分がp[i]となり、
A[n-i+1]…A[n] の(1,2)成分がq[i-1]、(2,2)成分がq[i]となります。
なので、A[1]…A[n] の(2,2)成分はp[n]でありq[n]でもあることになります。
また、A[1]…A[i] の第2行と A[i+1]…A[n] の第2列の積が A[1]…A[n] の(2,2)成分になるこ
ともわかります。
参考までに、
a[i]が正の整数のとき、A[i]は有理数の正則連分数を計算するための行列です。
A[1]…A[n] の(1,2)成分と(2,2)成分が分子と分母（または分母と分子）になります。
わたしが用意していた解答はこちら。
行列・ベクトルの転置を t(・) と書くことにする。
2次正方行列 A[i]=[[0,1],[1,a[i]]] (i=1,…,n) ，
列ベクトル b=t([0,1]) ，
列ベクトル u[i]=t([p[i-1],p[i]]) (i=1,…,n) ，
列ベクトル v[i]=t([q[i-1],q[i]]) (i=1,…,n) ，
スカラー r=t(b)A[1]…A[n]b
とおく。
t(u[i])=t(b)A[1]…A[i] ，v[i]=A[n-i+1]…A[n]b
となることを帰納法により示すことができる。（証明略）
p[n]=t(u[n])b=t(b)A[1]…A[n]b=r ，q[n]=t(b)v[n]=t(b)A[1]…A[n]b=r ，
p[i-1]q[n-i-1]+p[i]q[n-i]=t(u[i])v[n-i]=t(b)A[1]…A[i]A[i+1]…A[n]b=r
より、 p[n]=q[n]=p[i-1]q[n-i-1]+p[i]q[n-i]
DD++さんからのコメントです。（令和２年８月１７日付け）
なるほど、3項間漸化式なら2次正方行列という発想は出てくるべきでした。
各行列 A[i] が対称行列なので、A[1]*……*A[n] の転置が A[n]*……*A[1] になる、という
のが逆順の正体だったのですね。いやはや、うまいことできてるものです。
ＧＡＩさんからのコメントです。（令和２年８月２０日付け）
DD++さんの
この {r[n]} ですが、数列 {b[n]} の隣接しない何項かを選択して積をとる（何も選択しなかっ
た場合、積は1とする）全パターンの総和になっています。
という事実が面白かったので実験してみました。
A=[1,2,3]であるとき、隣り合わないものでのすべての積が作る和Sについて調べると、
S=1+2+3+1*3=9
A=[1,2,3,4]であるときは、 S=1+2+3+4+(1*3+1*4+2*4)=10+15=25
同じく、A=[1,2,3,4,5]なら、S=1+2+3+4+5+(1*3+1*4+1*5+2*4+2*5+3*5)+1*3*5=15+45+15=75
A=[1,2,3,4,5,6]なら、
S=1+2+3+4+5+6+(1*3+1*4+1*5+1*6+2*4+2*5+2*6+3*5+3*6+4*6)+
(1*3*5+1*3*6+1*4*6+2*4*6)=21+105+105=231
A=[1,2,3,4,5,6,7]なら、
S=1+2+3+4+5+6+7+(1*3+1*4+1*5+1*6+1*7+2*4+2*5+2*6+2*7+3*5+3*6+3*7+4*6+4*7+5*7)+
(1*3*5+1*3*6+1*3*7+1*4*6+1*4*7+1*5*7+2*4*6+2*4*7+2*5*7+3*5*7)+(1*3*5*7)
=28+210+420+105=763
と元のA集合が増えていくと、ますますこの合計Sを求めて行くことが困難になっていく。
ところが、この合計値に+1したものの 10,26,76,232,764,･･･ についての数は、DD++さんの
情報から、例えば、
A= [1, 2, 3, 4, 5, 6, 7]なら、
gp > M=vector(#A+1);M[1]=1;}for(j=2,#M,M[j]=1/(A[j-1]*M[j-1]));M
% = [1, 1, 1/2, 2/3, 3/8, 8/15, 5/16, 16/35]
gp > p(n)=if(n==0,1,n==1,M[1],M[n]*p(n-1)+p(n-2));
で定義しておけば、
gp >S=p(#M)/prod(k=1,#M,M[k]);S
%= 764
でこの値が求まる。
さらに、一般的には150年前でのエルミート多項式なるものの式（polhermite(n))
gp > for(n=1,10,print(n";"polhermite(n)))
1;2*x
2;4*x^2 - 2
3;8*x^3 - 12*x
4;16*x^4 - 48*x^2 + 12
5;32*x^5 - 160*x^3 + 120*x
6;64*x^6 - 480*x^4 + 720*x^2 - 120
7;128*x^7 - 1344*x^5 + 3360*x^3 - 1680*x
8;256*x^8 - 3584*x^6 + 13440*x^4 - 13440*x^2 + 1680
9;512*x^9 - 9216*x^7 + 48384*x^5 - 80640*x^3 + 30240*x
10;1024*x^10 - 23040*x^8 + 161280*x^6 - 403200*x^4 + 302400*x^2 - 30240
での変形式 2^(-n/2)*polhermite(n) でのxをt/sqrt(2)で置換した式で、更にtをI(虚数単位）
に置き換え、それをI^nで割る操作をしてやることで、A=[1,2,3,･････････,n]での一連の値が求
まるという。（この数列から1を引けばよい。）
その様子が次のプログラムで見れる。
gp > for(n=2,21,print(n-1";"substpol(substpol(2^(-n/2)*polhermite(n),x,t/sqrt(2)),t,I)/I^n))
1;2.0000000000000000000000000000000000000
2;4.0000000000000000000000000000000000000
3;10.000000000000000000000000000000000000
4;26.000000000000000000000000000000000000
5;76.000000000000000000000000000000000000
6;232.00000000000000000000000000000000000
7;764.00000000000000000000000000000000000
8;2620.0000000000000000000000000000000000
9;9496.0000000000000000000000000000000000
10;35696.000000000000000000000000000000000
11;140152.00000000000000000000000000000000
12;568504.00000000000000000000000000000000
13;2390480.0000000000000000000000000000000
14;10349536.000000000000000000000000000000
15;46206736.000000000000000000000000000000
16;211799312.00000000000000000000000000000
17;997313824.00000000000000000000000000000
18;4809701440.0000000000000000000000000000
19;23758664096.000000000000000000000000000
20;119952692896.00000000000000000000000000
即ち、A=[1,2,3,･･･,20]の行列から隣り合わないもののあらゆる積の和Sは、S=119952692895
になることが起きる。
（どんな場合があるかをしらみつぶしに探す手間を考えるだけで怖気てしまう。）
