+y= (a+b)(c+d)=(ac+bd)+(2ad+bc) ◆宮城県 アンパンマン さんからの解答。
【基本形】
1)
1+1=2, (m0,n0)=(1,1)
(mi+1,ni+1)=(3mi+4ni,2mi+3ni) ;i≧0 とおくと
2ni+12-mi+12
=2(2mi+3ni)2-(3mi+4ni)2
=2ni2-mi2
=1
無限に存在する。
2)
2a2-b2=1, c2-2d2=1 を満たす整数 a,b,c,dがあるとします。
x+y= (a+b)(c+d)=(ac+bd)+(2ad+bc)
x-y= (a-b)(c-d)=(ac+bd)-(2ad+bc)
2x2-y2=(2a2-b2)(c2-2d2)=1
つまりx=ac+bd, y=2ad+bcも 2n2-m2=1を満たします。
(a,b)の一番小さい非自明な解は(m0,n0)=(1,1)で、
(c,d)の一番小さい非自明な解は(c,d)=(3,2)です。
ni+1+mi+1
=(mi+ni√2)(3+2)
=(3mi+4ni)+(2mi+3ni)
(mi+1,ni+1)
=(3mi+4ni,2mi+3ni)
帰納法で
ni+mi
=(+1)2i+1
=(+1).(2+3)i
もしある(m,n)=(p,q)が
ni+mi=(+1)(2+3)iで表せないとします。
(p+q)/(+1)
=(p+q)(-1)
=2p-q+(q-p)
(r=2p-q,s=q-pがr2-2s2=1を満たします。)
あるkが,
(p+q)/｛(+1)(2+3)k｝
=(p+q)(-1)(3-2)k
＝g+h, 1＜g＜3，0＜h＜2.
g2-2h2とg,hが整数なので
(c,d)の一番小さい非自明な解は(c,d)=(3,2)であることと矛盾します。
つまりすべての解(m,n)は
ni+mi
=(+1)(2+3)i
=(+1)2i+1で表せます。
ni+mi
=[ni-1+mi-1](2+3)
=4ni-1+3mi-1+(2mi-1+3ni-1)
mi=4ni-1+3mi-1,
ni
=2mi-1+3ni-1
=3ni-1+2√(2ni-12-1), n0=1.
【図形問題風】
[z-(2z-u)]/[1+z(2z-u)]=[(2z+u)-z]/[1+(2z+u)z]
書き換えると
(u-z)/(u+z)＝(2z2+1-zu)/(2z2+1+zu)。
つまり u2-2z2=1
上と似た理由で
zi+ui
=(2+3)i
=(+1)2iは
u2-2z2=1を満たすので、無限にあります。
上と似た理由ですべての解(z,u)は
zi+ui
=(2+3)i
=(+1)2iで表せます。
つまり漸化式は上と同じ、
zi=3zi-1+2√(2zi-12+1), z0=2.
【整数論風】
(2m+1)2=2(2n+1)2-1
p=2m+1,q=2n+1とします。
【基本形】の時から
pi=4qi-1+3pi-1,
qi=2pi-1+3qi-1がわかります。
帰納法よりpi,qiが奇数であることがわかります。
つまり
ni
=[2pi-1+3qi-1-1]/2
=[6ni-1+2√(2(2ni-1+1)2-1)]/2+1, n0=2.
しかも(m,n)が無限に存在します。
【数論風】
2-m2/n2=1/n2 →2n2-m2=1
基本形の答えと同じです。
【数値計算法風】
1)
y=(4+3y)/(3+2y) →y=± (収束値）
(4-3)/(3-2)
=-
→ -は-に収束する。
(4+3y)/(3+2y)≧0 →ｙ≧-4/3,y＜-3/2の場合はに収束します。
(4+3y)/(3+2y)≧ｙ → ≧ｙ≧-,y＜-3
つまり
-4/3≧yi-1＞-の場合、
ｙi＞yi-1, に収束します。
-＞yi-1≧-3/2の場合、
ｙi＜yi-1、-に収束しないので, に収束します。
（ただしyi=-3/2(つまりｙi-1=(-15±√33)/12) の場合は
yi+2=3/2とします。
− には y0=− を除き - に収束しません。
2)
(4+3m/n)/(3+2m/n)=(4n+3m)/(3n+2m)
(4n+3m)2-2(3n+2m)2=m2-2n2
つまり y0=r/s, r2-2s2=1であれば
yiもｍ2=2ｎ2+1
3)
xi-1=p/q
→ xi=(p2+2q2)/(2pq)
p2-2q2=1
→ (p2+2q2)2-2(2pq)2=(p2-2q2)2=1
y0=3/2から、
ｍ2=2ｎ2+1を満たすすべての正数m/nは{yi}で表せますので
数列 xiは数列 yiの部分です。
4)
yi=xj=m/n
→xj+1=(m2+2n2)/(2mn)
yi+1=(3m+2. 2n)/(2m+3n),
yi+2=(17m+2. 12n)/(12m+17n)
帰納法より y2i+1=(m2+2n2)/(2mn)。
x0=y0,x1=y1,x2=y3から
おまけ）
値＜0の場合ｙ式を使います。
値＞0の場合ｘ式を使います。
提案：
ｙ式をもっと早く収束させるために,
x3=665857/470832より
yi+1=(941664+665857yi)/(665857+470832yi)
を使うと計算量は1/8に減ります。
◆出題者のY．M．Ojisan さんからのコメント。
ご提案の方法は、問題の意図とは若干とずれるところがあります。
Ｘの３番目の意味を方を重視した場合、初期値によりＸ3はからもう少し遠かったり、負であるかもかもしれません。
一方、665857/470832の方を重視した場合は、異なる手法を用いることになります。
さらに問題からはなれて、御趣旨である別の方法の提案としては、Ｘの４番目ならさらに早いのであって、Ｘの３番目の値が、何か特に見つけられやすいというような特異性があるわけではないと思います。