かなり小さい \(A,B,C\) について実験により答えを求める方法です。

\(f(x,y,z)\) をDPにより \(1 \leq x,y,z \leq 500\) すべてについて求めておきます。

\(D_n := f(An,Bn,Cn)\) として、\((D_1,D_2, \ldots)\) が p-recursive であるかを適切なライブラリに入力して確認すると、 \(g_0(i) \cdot D_i = g_1(i) \cdot D_{i-1} + \cdots + g_K(i) \cdot D_{i-K}\) が成立するような多項式 \(g_0, \ldots, g_K\) が実際に得られます。

\(g_0, \ldots, g_K\) のうちの最高次数を \(d\) とおくと、 漸近的には \([x^d]g_0 \cdot D_i \sim [x^d]g_1(i) \cdot D_{i-1} + \cdots + [x^d]g_K(i) \cdot D_{i-K}\) が成立していそうです。なのでこの特性方程式を、(答えの分数として有り得そうなものを全探索するなどして)解きます。

うまく探索すれば、\((A,B,C) = (2,2,1), (3,3,1), (4,4,1), (3,2,2), (4,3,2), (5,4,2), (6,5,2)\) などについて追加で分数の形で解が得られ、答えがどのような式になるかの考察に役立ちます。