3

a_{n+12}=a_{n+9}+a_{n+8}+a_{n+7}-a_{n+5}-a_{n+4}-a_{n+3}+a_nの漸化式が持つ不思議な性質

185
0

問題

a0=a1=a2=a3=a4=a5=a7=a8=0,a6=a9=a10=a11=1
an+12=an+9+an+8+an+7an+5an+4an+3+annZ
とするときa1013a1012a45を求めよ。

不思議な性質を説明する前にまずこの問題を愚直に解いてみる。

この漸化式の特性方程式が(x31)(x41)(x51) であるので
bn=an+3anとし、cn=bn+4bnとするとcn+5=cnかつc0=c1=c2=c3=0,c4=1
cn={0n4(mod5)1n4(mod5)
よってcn+16+cn+12+cn+8+cn+4+cn=1
(bn+20bn+16)+(bn+16bn+12)+(bn+12bn+8)+(bn+8bn+4)+(bn+4bn)=1
bn+20=bn+1
bn+20k=bn+kとなる。
an+60an=i=019bn+3i=i=06bn+3i+i=06bn+3i+21+i=05bn+3i+42=i=06bn+3i+i=06bn+3i+1+i=05bn+3i+2+7+12=i=019bn+i+19
Bn=i=019bn+iと置くと
an+60an=Bn+19となる。
Bn+1=i=019bn+1+i=i=119bn+i+bn+20=i=019bn+i+1=Bn+1であり、B0=11であるからBn=n+11
an+60kan=j=0k1(an+60(j+1)an+60j)=j=0k1(Bn+60j+19)=j=0k1(60j+n+30)=30k(k1)+k(n+30)
これを使うと
a1013=a60177=301716+1723+a7
a1012=a60178=301716+1722+a8
a45=a6015=a15+15
簡単な計算でa7=a8=0,a15=2を得るから
a1013a1012a45=17+a7a815a15=0
よって求める値は0である。

これでも十分良問だがもっとこの問題について掘り下げていく。実は0になったのはたまたまではない。上の数列を含むある数列は以下のような性質がある。

性質

an+12=an+9+an+8+an+7an+5an+4an+3+annZ
an=ann=1,2,3,4,5,6
a5+a0=a4+a3
を数列{an}が満たすならば
p2+q2=r2+s2を満たす任意の整数p,q,r,sにおいて
ap+aq=ar+asが成り立つ。

確かに上の具体例はこれを満たしている。先ほどの上の解答からanを機械的に計算できるのでとんでもない数の場合分けを行えば上の性質を証明できそうではあるが別の方法で示す。厳密に証明を書くと長くなって(面倒くさいので)しまうので簡単に証明のプロセスを下に書く。
step 1. an+24=an+18+an+16+an+14an+10an+8an+6+an
  an=an

証明
an=anはすぐに従うので省略。
上についてもan+12=an+9+an+8+an+7an+5an+4an+3+anを用いればすぐに証明できる。以降、akkが負のときはan=anが解決してくれるので非負のときのみ考える。

step 2. a2n+m+an2m=a2nm+an+2m
証明
(a2(n3)+m+a2(n4)+m+a2(n5)+ma2(n7)+ma2(n8)+ma2(n9)+m+a2(n12)+m)+(an32m+an42m+an52man72man82man92m+an122m)
=(a2(n3)m+a2(n4)m+a2(n5)ma2(n7)ma2(n8)ma2(n9)m+a2(n12)m)+(an3+2m+an4+2m+an5+2man7+2man8+2man9+2m+an12+2m)と変形できるのでnについての帰納法から0n11,mZ0のみを示せば良いが、m,nは対称的であるから0m11,nZ0を示せば良く、同じ議論から0n11,0m11を示せば良くこれは有限回の計算で示せる。(m,nが負のときはan=anから非負のときに帰着できる。)

step 3. akn+m+ankm=aknm+an+km
証明
step 2.の式にnn+m,mnmとすることでk=3の等式を得る。以降、kについての帰納法で示す。
k=2tのとき
a2tn+ma2tnm=atn+2matn2m=an+2tman2tmより成り立つ。ただし、最後の変形は帰納法の仮定を用いた。
k=2t+15のとき
step 2.の式にntn,mn+m,nmとすると
a(2t+1)n+m+a(t2)n2m=a(2t1)nm+a(t+2)n+2ma(2t+1)nm+a(t2)n+2m=a(2t1)n+m+a(t+2)n2m
(a(2t+1)n+ma(2t+1)nm)+(a(t2)n2ma(t2)n+2m)=(a(2t1)nma(2t1)n+m)+(a(t+2)n+2ma(t+2)n2m)mnを入れ替えて(a(2t+1)m+na(2t+1)mn)+(a(t2)m2na(t2)m+2n)=(a(2t1)mna(2t1)m+n)+(a(t+2)m+2na(t+2)m2n)
k=2t1,t+2,t2の帰納法の仮定を用いることでa(2t+1)n+m+an(2t+1)m=a(2t+1)nm+an+(2t+1)mを得る。(kが負のときはan=anから非負のときに帰着できる。)

step 4. p2+q2=r2+s2ap+aq=ar+as
証明
awy+xzawyxz=awxy+zawxyz=axy+wzaxywzawy+xz+axywz=axy+wz+awyxzであり
任意のp2+q2=r2+s2に対してあるw,x,y,zが存在してp=wy+xz,q=xywz,{r,s}={wyxz,xy+wz}が成り立つのが示せるのでそれを用いれば示したいものが示せる。

投稿日:2024111
更新日:222
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

はーい
はーい
22
2409

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中