ふしぎな数列

　　Franel number($Fr_n=\sum_{k=0}^{n}{ n \choose k }^3$)は、次の漸化式を満たします。
$(n+1)^2Fr_{n+1}=(7n^2+7n+2)Fr_n+8n^2Fr_{n-1} (n\geq1)$
Franel numberはその一般項の表示から、すべて整数ですが、この漸化式だけをみると、このことはとても非自明です。このような数列は他にもたくさんあります。（ アペリーの数列など ）
（リンク先のＰＤＦに$a_n=\sum_{i=0}^{n}{ n \choose k }^r (r\geq1)$が満たす漸化式について書かれています）
このような数列が存在すること自体が驚異ですが、「どうやってこんな数列と一般項を見つけたのか？」「一般項がこの漸化式を満たすことを、どうやって証明したのか？」」はとても気になる所です。
今回、このような漸化式を満たす数列を一つ見つけたので発見の経緯や証明を解説します。

注意：偶然と直感に頼る部分が多く含まれます。

今回見つけた数列

一般項$a_n=\sum_{k=0}^{n}{ n \choose k }^2{ n+k \choose k }$で定められる数列は、次の漸化式を満たす。

$(n+1)^2a_{n+1}=(11n^2+11n+3)a_n+n^2a_{n-1} (n\geq1)$

発見の経緯

　　このような非線形漸化式から一般項を求めることはとても難しいので、一般項から漸化式を推測します。
$a_n=\sum_{k=0}^{n}{ n \choose k }^2{ n+k \choose k }$はどこから出てきたかというと、アペリーの数列の一般項$\sum_{k=0}^{n}{ n \choose k }^2{ n+k \choose k}^2$の指数を少し変えたものです。
　　この$a_n$が整数$x_i$が存在して、
$(x_0n^2+x_1n+x_2)a_{n+1}=(x_3n^2+x_4n+x_5)a_n+(x_6n^2+x_7n+x_8)a_{n-1} (n\geq1)$　　
を満たすと仮定します。このことはFranel numberのΣの中身が二項係数３つの積だから、似た漸化式を満たしそうだなーとういう感覚からです。
あとはｎに１，２，…と自然数を代入し、９つの文字についての連立方程式を立てます。（定数項がないので不定方程式になる）
これを解いて最大公約数で割って、$x_0=x_2=x_6=1,x_1=2,x_3=x_4=11,x_5=3,x_7=x_8=0$を得ます。

すべてのｎについて漸化式を満たすことの証明

（ここでの証明は、 せいすうたん　1　整数たちの世界の奇妙な物語小林 銅蟲 (著), 関 真一朗 (著) ）
の「第５話アペリー数」を参考にしました）

　$a_{k,n}＝{ n \choose k }^2{ n+k \choose k }$と定義する。
$\sum_{k=0}^{n}((n+1)^2a_{k,n+1}-(11n^2+11n+3)a_{k,n}-n^2a_{k,n-1})+(n+1)^2a_{n+1,n+1}=0$を示せばよい。ここで、
　$A_{k,n}=(k^2+(6n+3)k-11n^2-9n-2)/({n \choose k }^2{ n+k \choose k})$
と定義する。

ここで

$(n+1)^2a_{k,n+1}-(11n^2+11n+3)a_{k,n}-n^2a_{k,n-1})+(n+1)^2a_{n+1,n+1}=A_{k,n}-A_{k-1,n}$

が成り立つ。というのも、
　　　（上式の左辺）×$k!(n-k+1)!^2/(n!(n+k-1)!)=(n + 1)^3(n + k + 1)(n + k) - (11n^2 + 11n + 3)(n - k + 1)^2(n + k)-n(n - k + 1)^2(n - k)^2$
であり、
　　　（上式の右辺）×$k!(n-k+1)!^2/(n!(n+k-1)!)=(k^2+(6n+3)k-11n^2-9n-2)(n-k+1)^2(n+k)-((k-1)^2+(6n+3)(k-1)-11n^2-9n-2)k!^3$

であるが、これらはともに
　　　$-k^4n + k^3(-7n^2-9n-3) + k^2(6n^3 + 30n^2 + 27n + 7) + k(17n^4 + 24n^3 + 3n^2 - 6n - 2) - 11n^5 - 31n^4 - 31n^3 - 13n^2 - 2n $

に等しいから。さて、
　　　　$A_{n,n}=-(2n+2)(2n+1)(2n)!/n!^2$
と
　　　　$(n+1)^2a_{n+1,n+1}=(2n+2)!/n!^2$
なので、$A_{n,n}=-(n+1)^2a_{n+1,n+1}$より、

\begin{multline} \begin{split} \sum_{k=0}^{n}((n+1)^2a_{k,n+1}-(11n^2+11n+3)a_{k,n}-n^2a_{k,n-1})+(n+1)^2a_{n+1,n+1} &=\sum_{k=0}^{n}(A_{k,n}-A_{k-1,n})+(n+1)^2a_{n+1,n+1}\\ &=A_{n,n}-A_{-1,n}+(n+1)^2a_{n+1,n+1}=0 \end{split} \end{multline}

が示された。

備考

　　$A_{k,n}$を唐突に定義しましたが、これは差分して$k!(n-k+1)!^2/(n!(n+k-1)!)$をかけたらちょうど等しくなってくれる多項式（もちろんこの多項式が存在することは非自明です）を見つけただけです。すると勝手に$A_{n,n}=-(n+1)^2a_{n+1,n+1}$となってくれたのでめでたし。発見の経緯からふりかえると一般項をうまく与えることができれば漸化式を見つけることはそこまで難しくないようです（逆に言えば、いわゆる漸化式を解くということはほぼ不可能？？）。

考察？

　　多項式×$a_n$が登場する漸化式と、二項係数の積の和の一般項の関係は深いようです。問題は、アペリーが$\zeta(3)$の無理性証明に利用したように、漸化式は同じで初期条件が異なる数列の一般項の表示を見つけることです。（詳しくはせいすうたん第５話を参照）こちらはまさしく漸化式を解く行為なのでどうやって見つければよいのか見当もつきません。すでに分かっている１つの初期条件についての一般項と深く関係があるのは間違いなさそうなのですが……

謝辞

　　ここまで読んで下さりありがとうございました。誤り等の指摘よろしくお願いいたします。