難しい漸化式の問題の作り方

はじめに

最近、次のような漸化式で表される数列の一般項をどうやって求めるのか、という質問を受けました。

この問題はもともと、 知乎@Lemniskate 氏と 知乎@开朗的向日葵 氏が作成した「第2回 一般項杯（通項杯）」の第14問として出題されたものです。
関連リンクは以下の通りです：
第1回 一般項杯： https://tieba.baidu.com/p/7518757717
第1回 一般項杯
第1回 一般項杯 解答： https://zhuanlan.zhihu.com/p/407534999
第2回 一般項杯： https://tieba.baidu.com/p/7559954240
第2回 一般項杯
第2回 知乎の関連質問： https://www.zhihu.com/question/490089610

一般項の求め方

帰納法を用いる

さて、元の問題に戻りましょう。この問題をどのように解くのでしょうか？

解答： $a_{n+1}+2a_{n}=a_{n-1}^2-2a_{n-1}$ と変形し、$a_{n+2}+2a_{n+1}=a_n^2-2a_n$ を得ます。その後、平方完成します：
$$ a_{n+2}+2a_{n+1}+1=(a_n-1)^2 $$
ここで $b_n=a_n-1$ とおくと、次のようになります：
$$ b_{n+2}+2b_{n+1}=b_n^2-4,b_0=0,b_1=-\frac{3}{4},b_2=-\frac{5}{2},b_3=\frac{25}{16} $$
このとき、$b_3=\frac{25}{16}=\frac{(-5/2)^2}{4}=\frac{b_2^2}{4}$ であることに気づきます。
したがって、次のように推測できます：
$$ \begin{cases} b_{2k+1}=\frac{b_{2k}^2}{4} \\ b_{2k+2}=\frac{b_{2k}^2}{2}-4 \end{cases} $$
数学的帰納法の使用を考えます：
$k=1$ のとき、$b_3=\frac{b_2^2}{4},b_4=-\frac{7}{8}=\frac{(-5/2)^2}{2}-4=\frac{b_2^2}{2}-4$。
$k=m+1:$ $b_{n+2}=b_n^2-b_{n+1}-4$ より
$n=2m+1$ とおくと：
$$ \begin{aligned} b_{2m+3}&=b_{2m+1}^2-2b_{2m+2}+4\\ &=\Bigl( \frac{b_{2m}^2}{4} \Bigr)^2-2\Bigl( \frac{b_{2m}^2}{4}-4 \Bigr)-4=\frac{b_{2m}^4}{16}-b_{2m}^2+4\\ \frac{b_{2m+2}^2}{4}&=\frac{1}{4}\Bigl( \frac{b_{2m}^2}{4}-4 \Bigr)^2\\ &=\frac{1}{4}\Bigl( \frac{b_{2m}^2}{4}-4b_{2m}^2+16\Bigr)\\ &=\frac{b_{2m}^4}{16}-b_{2m}^2+4 \end{aligned} $$
ゆえに $b_{2m+3}=\frac{b_{2m+2}^2}{4}$。
$n=2m+2$ とおくと：
$$ \begin{aligned} b_{2m+4}&=b_{2m+2}^2-2b_{2m+3}-4\\ &=b_{2m+2}^2-2\Bigl( \frac{b_{2m+2}^2}{4} \Bigr)-4\\ &=\frac{b_{2m+2}^2}{2}-4 \end{aligned} $$
したがって推測は成り立ちます。すなわち
$$ \begin{cases} b_{2k+1}=\frac{b_{2k}^2}{4} \\ b_{2k+2}=\frac{b_{2k}^2}{2} - 4 \end{cases} $$
$x_k=b_{2k}$ とおくと
$$ x_{k+1}=\frac{x_k^2}{2}-4,x_1=b_2=-\frac{5}{2}$$
$y_k=\frac{1}{4}x_k$ とおくと
$$ y_{k+1}=2y_k^2-1,y_1=\frac{x_1}{4}=-\frac{5}{8}$$
$\theta_k=\arccos y_k$ とおくと
$$ \cos \theta_{k+1}=2\cos^2\theta_k-1=\cos2\theta\qquad\theta_1=\arccos y_1=\arccos \Bigl( -\frac{5}{8} \Bigr)$$
これより
$$ b_{2k}=x_k=4y_k=4\cos(2^{k-1}\theta_1)$$
さらに
$$ b_{2k+1}=\frac{b_{2k}^2}{4}=4\cos^2(2^{k-1}\theta_1)=2+2\cos(2^{k-1}\theta_1)$$
元の変数に戻すと：
$$ a_n=\begin{cases} 1,&n=0; \\ \frac{1}{4},&n=1; \\ 4\cos(2^{k-1}\theta_1)+1,&n=2k,k\geq1; \\ 2\cos(2^k\theta_3)+1,&n=2k+1,k\geq1. \end{cases},\theta_1=\arccos \Bigl( -\frac{5}{8} \Bigr) $$
すなわち $a_0=1,a_1=\frac{1}{4}$
$$ a_n=\Bigl( 2\cos \Bigl( 2^{\frac{n}{2}-1}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)+\cos \Bigl( 2^{\frac{n-1}{2}}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)+2 \Bigr)+(-1)^n\Bigl( 2\cos \Bigl( 2^{\frac{n}{2}-1}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)-\cos \Bigl( 2^{\frac{n-1}{2}}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)-1\Bigr),\quad n\geq2 $$

未定係数法

この問題が「一般項杯」からの出題であることは知っています。お決まりのルールに従えば、帰納法は暗黙のうちに禁止（暗BAN）されているはずですので、別の方法を提示します：
解答： 変形すると
$$ b_{n+2}+2b_{n+1}=b_n^2-4$$
ここで次のように考えます
$$ b_{2k}=P\cos(\alpha_k)+Q,\qquad \alpha_{k+1}=2\alpha_k$$
$b_{2k+2}+2b_{2k+1}=b_{2k}^2-4$ に代入すると：
$$ P\cos(2\alpha_k)+Q+2b_{2k+1}=\Bigl( P\cos(\alpha_k)+Q \Bigr)^2-4=\frac{1}{2}P^2\cos(2\alpha_k)+2PQ\cos(\alpha_k)+\frac{1}{2}P^2+Q^2-4 $$
$P\neq 0$ より $2PQ=0\Rightarrow Q=0$ となり、さらに
$$ \begin{aligned} 2b_{2k+1}&=\Bigl( \frac{1}{2}P^2-P \Bigr)\cos(2\alpha_k)+\frac{1}{2}P^2-4\\ b_{2k+1}&=\frac{P^2-2P}{4}\cos(2\alpha_k)+\frac{P^2-8}{4} \end{aligned} $$
$b_{2k+3}+2b_{2k+2}=b_{2k+1}^2-4$ に代入すると
次のようになります
$$ \begin{aligned} &\frac{P^2-2P}{4}\cos(4\alpha_k)+2P\cos(2\alpha_k)+\frac{P^2-8}{4}\\ =&\Bigl( \frac{P^2-2P}{4}\cos(2\alpha_k)+\frac{P^2-8}{4} \Bigr)^2-4\\ =&\frac{P^4-4P^3+4P^2}{32}\cos(4\alpha_k)+\frac{P^4-2P^3-8P^2+16P}{8}\cos(2\alpha_k)+\frac{3P^4-4P^3-28P^2}{32} \end{aligned} $$
このとき、次を満たす必要があります
$$ \begin{cases} \frac{P^2-2P}{4}=\frac{P^4-4P^3+4P^2}{32} \\ 2P=\frac{P^4-2P^3-8P^2+16P}{8} \\ \frac{P^2-8}{4}=\frac{3P^4-4P^3-28P^2}{32} \end{cases}\Rightarrow P=4,-2 $$
実際には2つの値は整合しています。以下では $P=4$ を取ります。

最高周波数の項だけを比較することもできます。$\frac{P^2-2P}{4}=\frac{1}{2}\Bigl( \frac{P^2-2P}{4} \Bigr)^2\Rightarrow\frac{P^2-2P}{4}=0,2$。$2$ を取ると $P^2-2P-8=0\Rightarrow P=4,-2$ となります。

代入して戻すと
$$ \begin{aligned} b_{2k}&=4\cos(\alpha_k),\alpha_{k+1}=2\alpha_k\\ b_{2k+1}&=\frac{P^2-2P}{4}\cos(2\alpha_k)+\frac{P^2-8}{4}=2\cos(2\alpha_k)+2\\ \alpha_1&=\arccos \Bigl( \frac{1}{4}b_2 \Bigr)=\arccos \Bigl( -\frac{5}{8} \Bigr) \end{aligned} $$
すなわち $\alpha_k=2^{k-1}\arccos \Bigl( -\frac{5}{8} \Bigr)$
$$ \begin{aligned} b_n&=\Bigl( 2\cos \Bigl( 2^{\frac{n}{2}-1}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)+\cos \Bigl( 2^{\frac{n-1}{2}}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)+1 \Bigr)+(-1)^n\Bigl( 2\cos \Bigl( 2^{\frac{n}{2}-1}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)-\cos \Bigl( 2^{\frac{n-1}{2}}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)-1\Bigr),\quad n\geq2\\ a_n&=\Bigl( 2\cos \Bigl( 2^{\frac{n}{2}-1}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)+\cos \Bigl( 2^{\frac{n-1}{2}}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)+2 \Bigr)+(-1)^n\Bigl( 2\cos \Bigl( 2^{\frac{n}{2}-1}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)-\cos \Bigl( 2^{\frac{n-1}{2}}\arccos \Bigl( -\frac{5}{8} \Bigr) \Bigr)-1\Bigr),\quad n\geq2 \end{aligned} $$

ある種の数列の一般項の求め方

帰納法を用いた解法を見ると、あの「気づく」ステップはまるで天からの啓示のようで、到底真似できないと思うことでしょう。また、2つ目の解法を見ると、チェビシェフ多項式を利用する発想も突然降ってわいたように見え、なぜいきなり $b_{2k}=P\cos(\alpha_k)+Q,\alpha_{k+1}=2\alpha_k$ と置けるのか疑問に思うはずです。$a_{n+1}=pa_n+q$ を解くときのような、決まった定石（セオリー）はないのでしょうか？
実は、この漸化式は別の視点から捉えることができます。ここで、2次元アフィン空間 $\mathbb{A}^2$ 上の代数力学系を考えてみましょう：
$$ \begin{aligned} x_{n+1} &=x_n^2-2\\ y_{n+1} &=y_n^2-2 \end{aligned} $$
これらの数列の一般項を単独で求める方法は、三角関数による置換（三角置換）を行えばよいので、皆さんもよくご存知でしょう。では、これら2つの数列を用いて新しい漸化式を構築するにはどうすればよいでしょうか？ここで置換群（対称群） $S_2$ を導入します。対称式の基本定理（よく知らない方は、こちらのbilibili動画をご覧ください。非常に詳しく解説されています： 五整定理 ）によれば、$x,y$ に関する任意の対称多項式は、基本対称式の多項式として一意に表すことができます。2次元における基底は以下のようになります：
$$ \begin{aligned} S_n&=x_n+y_n\\ P_n&=x_ny_n \end{aligned} $$
これにより、$(\mathbb{A}^2,x_n,y_n)$ から $(\mathbb{A}^2/S_2,S_n,P_n)$ が構成されました。つまり、元の空間を置換群で割った商空間です。

もちろん、抽象代数学よりも線形代数学に親しみがある方は、一方がトレース（跡）で、もう一方が行列式であると考えても構いません。

このとき、次が成り立ちます：
$$ \begin{cases} S_{n+1}=x_{n+1}+y_{n+1}=(x_n^2-2)+(y_n^2-2)=(x_n+y_n)^2-2x_ny_n+4=S_n^2-2P_n-4 \\ P_{n+1}=x_{n+1}y_{n+1}=(x_n^2-2)(y_n^2-2)=(x_n^2y_n^2)-2(x_n^2+y_n^2)+4=P_n^2-2(S_n^2-2P_n)+4 \end{cases} $$
1つ目の方程式から $2P_n=S_n^2-S_{n+1}-4$ を得て、これを2つ目の方程式に代入すると：
$$ P_{n+1}=P_n^2-2S_{n+1}-4\Rightarrow 2P_{n+1}=2P_n^2-4S_{n+1}-4\Rightarrow S_{n+1}^2-S_{n+2}-4=2\Bigl( \frac{S_n^2-S_{n+1}-4}{2} \Bigr)^2 $$
すなわち
$$ \begin{aligned} S_{n+1}^2-S_{n+2}-4&=\frac{1}{2}(S_n^2-S_{n+1}-4)^2-4S_{n+1}-8\\ 2S_{n+2}&=2S_{n+1}^2+8S_{n+1}+8-(S_n^2-S_{n+1}-4)^2\\ &=2(S_{n+1}+2)^2-(S_n^2-S_{n+1}-4)^2\\ &=S_{n+1}^2+2S_{n+1}S_{n}^2-S_n^4+8S_n-8 \end{aligned} $$
これで新しい問題が得られました：

この時点で基底が分かっているので、直接次のように証明できます：
解： $a_n=x_n+y_n,x_{n+1}=x_n^2-2,y_{n+1}=y_{n}^2-2$ と置きます。
このとき、必ず次が成り立ちます。
$$ a_{n+1}=x_{n+1}+y_{n+1}=x_n^2+y_n^2-4 $$
ここで次のように構成します。
$$ P_n=x_ny_n $$
なぜなら、
$$ a_n^2=(x_n+y_n)^2=x_n^2+y_n^2+2x_ny_n=a_{n+1}+4+2P_n $$
ゆえに
$$ 2P_n=a_n^2-a_{n+1}-4 $$
次に以下を考えます。
$$ P_{n+1}=x_{n+1}y_{n+1}=(x_n^2-2)(y_n^2-2)=P_n^2-2(x_n^2+y_n^2)+4 $$
代入して戻すと、
$$ P_{n+1}=P_n^2-2(a_{n+1}+4)+4=P_n^2-2a_{n+1}-4 $$
$2P_{n+1}=a_{n+1}^2-a_{n+2}-4$ および $2P_n=a_n^2-a_{n+1}-4$ より：
$$ \begin{aligned} a_{n+1}^2-a_{n+2}-4&=2\Bigl( \frac{1}{2}(a_n^2-a_{n+1}-4) \Bigr)^2-4a_{n+1}-8\\ 2a_{n+1}^2-2a_{n+2}-8&=2a_{n+1}^2+8a_{n+1}+8-(a_n^2-a_{n+1}-4)^2 \end{aligned} $$
したがって、
$$ 2a_{n+2}=2(a_{n+1}+2)^2-(a_n^2-a_{n+1}-4)^2 $$
実はこのとき、漸化式そのものは利用しておらず、特定の性質を満たす $x_n,y_n$ を用いて $a_n=x_n+y_n$ とあらかじめ設定し、そこから問題の漸化式を導き出したに過ぎません。したがって、ここで設定した $a_n$ がまさに問題が求めている $a_n$ であるとみなすことができます。以降では、このように設定した $x_n,y_n,P_n$ が「相容性（整合性）」を満たすと呼ぶことにします。
次に $a_n$ の一般項を求めます。
条件より、
$$ \begin{cases} a_1=x_1+y_1=1\\ a_2=x_1^2+y_1^2-4=-2 \end{cases}\Rightarrow \begin{cases} x_1+y_1=1 \\ x_1y_1=-\frac{1}{2} \end{cases} $$
一般性を失わず、$x_1=\frac{1-\sqrt{3}}{2},y_1=\frac{1+\sqrt{3}}{2}$ と置くと、
$u_{n+1}=u_n^2-2,u_n=2\cos\theta_n,\theta_n=2^{n-1}\theta_1$ が成り立つため、
$$ \begin{aligned} x_1&=\frac{1-\sqrt{3}}{2}\Rightarrow2\cos\theta_{x_1}=\frac{1-\sqrt{3}}{2}\Rightarrow\theta_{x_1}=\arccos\frac{1-\sqrt{ 3 }}{4}\\ y_1&=\frac{1+\sqrt{3}}{2}\Rightarrow2\cos\theta_{y_1}=\frac{1+\sqrt{3}}{2}\Rightarrow\theta_{y_1}=\arccos\frac{1+\sqrt{ 3 }}{4} \end{aligned} $$
したがって、
$$ \begin{cases} x_n=2\cos \Bigl( 2^{n-1}\arccos\frac{1-\sqrt{3}}{4} \Bigr) \\ y_n=2\cos \Bigl( 2^{n-1}\arccos\frac{1+\sqrt{3}}{4} \Bigr) \end{cases} $$
よって、
$$ a_n=x_n+y_n=2\Bigl( \cos\Bigl( 2^{n-1}\arccos\frac{1-\sqrt{3}}{4} \Bigr)+\cos\Bigl( 2^{n-1}\arccos\frac{1+\sqrt{3}}{4} \Bigr) \Bigr). $$
証明過程を振り返ると、この種の数列は $u_{n+1}=u_n^2-2$ という数列に依存していることがわかります。あるクラスの $y_{n+1}=av_n^2+bv_n+c$ という数列の一般項について知っていれば、この種の数列が以下の2点に依存することがわかるはずです：

1. 係数 $a,b,c$ の判別式。
2. 初項 $v_1$ の値。
   ここで $u_{n+1}=u_n^2-2$ の係数は既に固定されているため、次に初項の影響について議論します：
   実際には、$u_1\in[-2,2]$ であれば、$u_1=2\cos\theta$ を満たす $\theta$ が必ず存在し、さらに $u_{n}=2\cos(2^{n-1}\theta)\in[-2,2]$ となります。そうでない場合は、$u_1=2\cosh\theta$ を満たす $\theta$ が必ず存在し、さらに $u_{n}=2\cosh(2^{n-1}\theta)=e^{2^{n-1}\theta}+e^{-2^{n-1}\theta}$ となります。
   したがって、もし $x_1,y_1\in[-2,2]$ であれば $2\cos\theta$ 型になります。このとき、$a_1=x_1+y_1,P_1=x_1y_1=\frac{a_1^2-a_2-4}{2}$ および解と係数の関係（ビエタの公式）より、$x_1,y_1$ は方程式 $t^2-a_1t+\frac{a_1^2-a_2-4}{2}=0$ の2つの解になるはずです。
   目標として、$t^2-a_1t+\frac{a_1^2-a_2-4}{2}=0$ の2つの解がともに実数であり、かつ $[-2,2]$ の範囲に収まるためには、$f(t)=t^2-a_1t+\frac{a_1^2-a_2-4}{2}$ は必ず以下を満たす必要があります：
   $$ \begin{cases} \Delta=a_1^2-4\Bigl( \frac{a_1^2-a_2-4}{2} \Bigr)=2a_2+8-a_1^2\geq0 \\ f(2)=2-2a_1+\frac{a_1^2}{2}-\frac{a_2}{2}\geq0 \\ f(-2)=2+2a_1+\frac{a_1^2}{2}-\frac{a_2}{2}\geq0 \end{cases}\Leftrightarrow \frac{1}{2}a_1^2-4\leq a_2\leq (a_1\pm2)^2 $$
   次に、$\cosh\theta$ に関する練習問題を見てみましょう：

方程式 $t^2-a_1t+\frac{a_1^2-a_2-4}{2}=t^2-11t+28=0$ の2つの解について考えます。一般性を失わず、以下のように置きます：
$$ \begin{cases} x_1=4 \\ y_1=7 \end{cases} $$
すると、
$$ \begin{cases} \theta_{x_1}=\mathrm{arccosh}\;2 \\ \theta_{y_1}=\mathrm{arccosh}\;\frac{7}{2} \\ \end{cases}\Rightarrow\begin{cases} x_n=2\cosh \Bigl( 2^{n-1}\mathrm{arccosh}\;2 \Bigr) \\ y_n=2\cosh \Bigl( 2^{n-1}\mathrm{arccosh}\;\frac{7}{2} \Bigr) \end{cases} $$
あるいは $u_n=k_n+\frac{1}{k_n}$ と置くと、
$$ \begin{aligned} x_1&=k_{x}+\frac{1}{k_x}=4\Rightarrow k_x=2\pm\sqrt{3}\Rightarrow x_n=(2+\sqrt{3})^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}\\ y_1&=k_{y}+\frac{1}{k_y}=7\Rightarrow k_y=\frac{7\pm3\sqrt{ 5 }}{2}\Rightarrow y_n=\Bigl( \frac{7+3\sqrt{ 5 }}{2} \Bigr)^{2^{n-1}}+\Bigl( \frac{7-3\sqrt{ 5 }}{2} \Bigr)^{2^{n-1}}\\ \end{aligned} $$
ゆえに、
$$ \begin{aligned} a_n=x_n+y_n&=2\cosh \Bigl( 2^{n-1}\mathrm{arccosh}\;2 \Bigr)+2\cosh \Bigl( 2^{n-1}\mathrm{arccosh}\;\frac{7}{2} \Bigr) \end{aligned} $$
この証明を見て、どこかで見覚えがあると感じたでしょうか。実はこれは、 第1回通項杯の第15問 、 タコ杯（章鱼杯）のある問題 、および2025年アメリカ代表選抜試験の第2問に類似しています（AoPS のリンクの引用方法がわからないため省略します）：

この問題の基底は $x_{n+1}=x_n^2,y_{n+1}=y_n^2$ であるため、次のように置きます：
$$ a_n=x_n+y_n+\frac{1}{x_ny_n},x_{n+1}=x_n^2,y_{n+1}=y_n^2 $$
そして、
$$ S_n=x_n+y_n,\quad P_n=x_ny_n $$
とすると、
$$ \begin{aligned} S_{n+1}&=x_n^2+y_n^2=S_n^2-2P_n\\ P_{n+1}&=x_n^2y_n^2=P_n^2 \end{aligned} $$
したがって、
$$ \begin{aligned} a_n&=S_n+\frac{1}{P_n}\\ a_{n+1}&=S_n^2-2P_n+\frac{1}{P_n^2}\\ a_{n+2}&=S_{n+1}^2-2P_{n+1}+\frac{1}{P_{n+1}^2}=(S_n^2-2P_n)^2-2P_n^2+\frac{1}{P_n^4}\\ &=S_n^4-4S_n^2P_n+2P_n^2+\frac{1}{P_n^4} \end{aligned} $$
これらを $a_{n+1}^2+2a_n^2a_{n+1}-a_n^4+8a_n$ に代入して整理すると、$2a_{n+2}=2S_n^4-8S_n^2P_n+4P_n^2+\frac{2}{P_n^4}$ となり、相容性を満たします。
また、
$$ \begin{cases} a_0=x_0+y_0+\frac{1}{x_0y_0}=11+\frac{1}{30} \\ a_1=x_0^2+y_0^2+\frac{1}{x_0^2y_0^2} \end{cases}\Rightarrow\begin{cases} x_0=5 \\ y_0=6 \end{cases}\Rightarrow\begin{cases} x_n=5^{2^n} \\ y_n=6^{2^n} \end{cases} $$
ゆえに、
$$ a_n=x_n+y_n+\frac{1}{x_ny_n}=5^{2^n}+6^{2^n}+30^{-2^n} $$
さらに分析を進めると、$x_1,y_1,\frac{1}{x_1y_1}$ に対応する方程式は $t^3-a_1t^2+\frac{a_1^2-a_2}{2}t-1=0$ の3つの解であることがわかります。
この種の問題の中で最もシンプルな構成（あくまで私の主観ですが）は、次のような問題になるはずです：

このとき、$x_{n+1}=x_n^2,y_{n+1}=y_n^2$ より、
$$ \begin{aligned} S_{n+1}&=S_n^2-2P_n,\quad P_{n+1}=P_n^2\\ a_{n}&=x_n^2+y_n^2=S_{n+1}=S_n^2-2P_n\\ a_{n+1}&=a_n^2-2P_n^2\\ a_{n+2}&=a_{n+1}^2-2P_n^4 \end{aligned} $$
これから $2P_n^2=a_n^2-a_{n+1}\Rightarrow 4P_n^4=(a_n^2-a_{n+1})^2=2(a_{n+1}^2-a_{n+2})$ を得て、展開すると
$$ 2a_{n+2}=a_{n+1}^2+2a_{n+1}a_n^2-a_n^4 $$
よって相容性を満たします。
また、
$$ \begin{cases} a_1=x_1^2+y_1^2=3 \\ a_2=x_1^4+y_1^4=7 \end{cases}\Rightarrow\begin{cases} x_1^2=\frac{3+\sqrt{5}}{2} \\ y_1^2=\frac{3-\sqrt{5}}{2} \end{cases} $$
したがって、
$$ a_n=(x_1^2)^{2^{n-1}}+(y_1^2)^{2^{n-1}}=\Bigl( \frac{3+\sqrt{5}}{2} \Bigr)^{2^{n-1}}+\Bigl( \frac{3-\sqrt{5}}{2}\Bigr)^{2^{n-1}} $$
もちろん、これは最もシンプルな構成であるため、以下のような状況に退化させることができます：
$$ \begin{aligned} (a_n^2-a_{n+1})^2&=2(a_{n+1}^2-a_{n+2})\\ b_n&=a_n^2-a_{n+1}\\ b_{n+1}&=\frac{1}{2}b_n^2,\qquad b_1=2\\ \Rightarrow a_n&=2\cos \Bigl( 2^{n-1}\arccos\frac{3}{2} \Bigr) \end{aligned} $$

この種の問題の生成方法

これまで、以下のような一般項を求める問題について議論してきました：

$a_1=3,a_2=7,2a_{n+2}=a_{n+1}^2+2a_{n+1}a_n^2-a_n^4$ のとき、数列 $\{a_n\}$ の一般項を求めよ。
$a_0=11+\frac{1}{30},a_1=61+\frac{1}{900},2a_{n+2}=a_{n+1}^2+2a_{n+1}a_n^2-a_n^4+8a_n$ のとき、数列 $\{a_n\}$ の一般項を求めよ。
$a_1=1,a_2=-2,2a_{n+2}=a_{n+1}^2+2a_{n+1}a_n^2-a_n^4+8a_n^2-8$ のとき、数列 $\{a_n\}$ の一般項を求めよ。
$a_0=1,a_1=\frac{1}{4},a_{n+1}=a_{n-1}^2-2a_{n-1}-2a_n$ のとき、数列 $\{a_n\}$ の一般項を求めよ。

解答に関する部分はここまでにして、今度はあなたが作問者になる番です。以下では、作問に用いるツール「グレブナー基底（Groebner basis）」について紹介します。詳しくなくても大丈夫です。ここでは具体的なアルゴリズムについては解説しません。その役割を理解するために、まずは簡単な問題を見てみましょう：

解：
$$ w=x^2+y^2=(x+y)^2-2xy=u^2-2v $$
したがって、$w-u^2+2v=0$ となります。
これは非常に簡単ですが、より一般的に、$u=f_1(x,y),v=f_2(x,y),w=f_3(x,y)$ から $x,y$ を正確に消去し、$u,v,w$ の関係式を得るにはどうすればよいでしょうか？
実はこれこそがグレブナー基底の役割であり、グレブナー基底は直接 $g(u,v,w)=0$ を導き出してくれます。Mathematicaを起動して、この例題がMMA（Mathematica）でどのように解かれるか見てみましょう。

      GroebnerBasis[{x + y - u, x y - v, x^2 + y^2 - w}, {u, v, w}, {x, y}]
Reduce[First[%] == 0, w]
    

Mahtematica Code

コードを見ると、実際には GroebnerBasis[{関係式の集まり}, {残したい変数}, {消去したい変数}] となっていることがわかります。
素晴らしい！これでグレブナー基底の使い方はマスターしましたね！
では、この問題を例として、実際に問題を作ってみましょう：

Step1：基底 $x_{n+1}\mapsto x_n^2,y_{n+1}\mapsto y_n^2$ を確認する。
Step2：対称式の基本定理に基づき、$S_n=x_n+y_n,P_n=x_ny_n$ を選択する。
Step3：$a_n$ を構築し、$a_n=S_n+\frac{1}{P_n}$ と置く。
Step4：基底の数に基づいて、$n$ から $n+1$ に漸化させて次を得る。
$$ \begin{aligned} a_n&=S_n+\frac{1}{P_n}\\ a_{n+1}&=S_n^2-2P_n+\frac{1}{P_n^2}\\ a_{n+2}&=S_{n+1}^2-2P_{n+1}+\frac{1}{P_{n+1}^2}=(S_n^2-2P_n)^2-2P_n^2+\frac{1}{P_n^4}\\ &=S_n^4-4S_n^2P_n+2P_n^2+\frac{1}{P_n^4} \end{aligned} $$
Step5：グレブナー基底を用いて変数を消去し、漸化式を得る。

      GroebnerBasis[{a0 == s + 1/p, a1 == s^2 - 2 p + 1/p^2, 
  a2 == s^4 - 4 s^2 p + 2 p^2 + 1/p^4}, {a0, a1, a2}, {s, p}]
    

Mahtematica Code

すなわち $-8a_n+a_n^4-2a_n^2a_{n+1}-a_{n+1}^2+2a_{n+2}=0$。
Step6：漸化式を整理する：$2a_{n+2}=a_{n+1}^2+2a_{n+1}a_n^2-a_n^4+8a_n$。
Step7：基底の初項を $x_1=5,y_1=6$ と設定し、数列の初項 $a_1=11+\frac{1}{30}$ を得る。
これで問題の完成です。

もう一歩進んでみると

（これは原稿部分の内容であり、後でどのように修正されるかは誰にもわかりません。以下の内容はあくまで直感であり、厳密なものではないことを事前にお断りしておきます。）
前述の7つのステップによる作問過程において、実は私たちは暗黙のうちに多くの制約を設けていました。このセクションでは、これらの制約がどのようにして生じたのかを説明します。
まず、基底をどのように決定するかについてですが、基底の決定は多項式力学系 $x\mapsto P(x)$ に従います。初等的な閉じた形の解（閉形式の解）を持つためには、以下の3つの力学系のいずれかと同型であるしかありません：

1. べき乗（冪乗）：$x\mapsto x^k$、例えば $a^{k^n}$ のようなもの。
2. チェビシェフ多項式：$x\mapsto 2\cos(k\arccos(\frac{x}{2}))$、すなわち $x^2-2,x^3-3x$ のような三角置換の類。
3. 分数線形変換 / メビウス変換：$x\mapsto\frac{ax+b}{cx+d}$。
   次に、複数の基底の規則が一致していることを保証する必要があります。
   さらに、上記の問題の多くは $\mathbb{A}^n/S_n$ を選択しています。例えば $\mathbb{A^2}/S_2$ ですが、これは $a_n$ が $x_n,y_n$ について対称であることを必須とします。$S_2$ に対応する不変環の生成元は、まさに対称式の基本定理における $e_1=x_n+y_n$ と $e_2=x_ny_n$ であり、したがって自然に $S_n=x_n+y_n,P_n=x_ny_n$ となります。
   実際には、割る群（商をとる群）を変更することができます。例えば $\mathbb{A^3}/C_3$ です。ここで $C_3$ は3次の巡回群です。最もシンプルな（これも筆者の主観ですが）基底を次のように選びます：
   $$ x_{n+1}=x_n^2,\quad y_{n+1}=y_n^2,\quad z_{n+1}=z_n^2 $$
   このとき、$C_3$ に対応する不変式は以下のようになります：
   $$ \begin{aligned} e_1&=x+y+z\\ e_2&=xy+yz+zx\\ e_3&=xyz\\ l&=xy^2+yz^2+zx^2\\ r&=x^2y+y^2z+z^2x \end{aligned} $$
   ここでは $C_3$ の性質を反映させるため、$l,r$ の2つを我々の $S_n,P_n$ として選びます（ただし、後ほどこれらを $L_n,R_n$ と呼ぶことにします）。
   したがって、ここのStep3では次のように選択します：
   $$ \begin{aligned} a_n&=L_n=x_ny_n^2+y_nz_n^2+z_nx_n^2\\ b_n&=R_n=x_n^2y_n+y_n^2z_n+z_n^2x_n \end{aligned} $$
   方程式の数が増えたため、Step4では1回だけ漸化させればよく、次を得ます：
   $$ \begin{aligned} a_{n+1} &= x_{n+1} y_{n+1}^2 + y_{n+1} z_{n+1}^2 + z_{n+1} x_{n+1}^2 \\ &= x_n^2 y_n^4 + y_n^2 z_n^4 + z_n^2 x_n^4 \\ b_{n+1} &= x_{n+1}^2 y_{n+1} + y_{n+1}^2 z_{n+1} + z_{n+1}^2 x_{n+1} \\ &= x_n^4 y_n^2 + y_n^4 z_n^2 + z_n^4 x_n^2 \end{aligned} $$
   Step5：グレブナー基底を用いて $(x_n,y_n,z_n)$ を消去する：
   問題の簡潔さを保つため、さらに1つの制約を追加する必要があります。$P_n=x_ny_nz_n$ とすると、次が成り立ちます：
   $$ P_{n+1}=x_{n+1}y_{n+1}z_{n+1}=x_n^2y_n^2z_n^2=P_n^2 $$
   便宜上 $P_1=1$ とすると、必然的に $x_ny_nz_n=1$ となります。つまり、追加する制約は $x_ny_nz_n=1$ です。その後、グレブナー基底を使用します：

      GroebnerBasis[{
  a0 == x y^2 + y z^2 + z x^2,
  b0 == x^2 y + y^2 z + z^2 x,
  a1 == x^2 y^4 + y^2 z^4 + z^2 x^4,
  b1 == x^4 y^2 + y^4 z^2 + z^4 x^2,
  x y z == 1}, {a0, b0, a1, b1}, {x, y, z}]
    

Step6：得られた結果に基づいて {-4 a1 - 8 b0 + b0^4 - 2 b0^2 b1 + b1^2, 2 a0 - b0^2 + b1} を整理します。すなわち
$$ \begin{aligned} -4a_{n+1}-8b_n+b_n^4-2b_n^2b_{n+1}+b_{n+1}^2&=0\\ 2a_n-b_n^2+b_{n+1}&=0 \end{aligned} $$
まず2つ目の方程式から $b_{n+1}=b_n^2-2a_n$ を得て、これを1つ目の方程式に代入すると、
$$ \begin{aligned} -4a_{n+1}-8b_n+b_n^4-2b_n^2b_{n+1}+b_{n+1}^2&=-4a_{n+1}-8b_n+(b_n^2-b_{n+1})^2\\ &=-4a_{n+1}-8b_n+4a_n^2=0 \end{aligned} $$
すなわち $a_{n+1}=a_n^2-2b_n$ となり、連立させると次が得られます：
$$ \begin{cases} a_{n+1}=a_n^2-2b_n \\ b_{n+1}=b_n^2-2a_n \end{cases} $$
Step7：基底の初項を設定します。ここでは追加で次のように置くことができます：
$$ U_n=x_ny_n^2,\quad V_n=y_nz_n^2,\quad W_n=z_nx_n^2 $$
このとき、次が成り立ちます：
$$ \begin{aligned} L_n&=U_n+V_n+W_n\\ R_n&=U_nV_n+V_nW_n+W_nU_n\\ 1&=U_nV_nW_n \end{aligned} $$
$U_1=5,V_1=6,W_1=\frac{1}{30}$ と設定すると、$a_1=11+\frac{1}{30},b_1=30+\frac{11}{30}$ が得られます。これで問題が完成しました。

お気づきかもしれませんが、これが タコ杯（章鱼杯）のある問題 の元問題です。以前は $\mathbb{A^2}/S_2$ の下で作成されましたが、今回は $\mathbb{A^3}/C_3$ の下で作成されました。本来であれば異なるはずなのに、なぜ得られる問題が同じになるのでしょうか。その理由は、$x_ny_nz_n=1$ という制約を追加したため、この制約の下では $\mathbb{A^2}/S_2$ と $\mathbb{A^3}/C_3$ が同型になるからです。
これはさらに、もし $P_1=k$ であれば、次のようになることを示しています：
$$ \begin{cases} a_{n+1}=a_n^2-2P_nb_n\\ b_{n+1}=b_n^2-2P_na_n \end{cases}\Rightarrow\begin{cases} a_{n+1}=a_n^2-2k^{2^{n-1}}b_n\\ b_{n+1}=b_n^2-2k^{2^{n-1}}a_n \end{cases} $$
このとき $\hat{a}_n=\frac{a_n}{P_n},\hat{b}_n=\frac{b_n}{P_n}$ と置けば、次が得られます：
$$ \begin{cases} \hat{a}_{n+1}=\hat{a}_n^2-2\hat{b}_n \\ \hat{b}_{n+1}=\hat{b}_n^2-2\hat{a}_n \\ \end{cases} $$
したがって、解くことが可能になります。
この作問テンプレートの汎用性を示すために、次に基底を変更し、さらに複雑な連立漸化式（結合漸化式数列）の問題をいくつか提示します：
Step1：基底 $S_{n+1}\mapsto\frac{1}{2}\Bigl( S_n+\frac{12}{S_n} \Bigr),D_{n+1}\mapsto\frac{1}{2}\Bigl( D_n+\frac{12}{D_n} \Bigr)$ を確認する。
Step2：$U_n=S_n^2+D_n^2,V_{n}=S_nD_n$ を選択する。
Step3：$a_n,b_n$ を構築する：
$$ \begin{cases} a_n=\frac{S_n^2+D_n^2}{4}-4 \\ b_n=\frac{S_nD_n}{4\sqrt{3}} \end{cases} $$
Step4：漸化させて $a_{n+1},b_{n+1}$ を得る：
$$ \begin{aligned} a_{n+1}&=\frac{S_{n+1}^2+D_{n+1}^2}{4}-4=\frac{1}{4} \Bigl( \frac{1}{4}\Bigl(S_n + \frac{12}{S_n}\Bigr)^2 + \frac{1}{4}\Bigr(D_n + \frac{12}{D_n}\Bigr)^2 \Bigr) - 4\\ b_{n+1}&=\frac{S_{n+1}D_{n+1}}{4\sqrt{3}}=\frac{1}{4\sqrt{ 3 }}\Bigl( \frac{1}{2}\Bigl( S_n+\frac{12}{S_n} \Bigr)\frac{1}{2}\Bigl( D_n+\frac{12}{D_n} \Bigr) \Bigr) \end{aligned} $$
さらに
$$ \begin{aligned} a_{n+1}&=\frac{1}{16}\Bigl((S_n^2+D_n^2)+144\frac{S_n^2+D_n^2}{S_n^2D_n^2}\Bigr)-1\\ b_{n+1}&=\frac{1}{16\sqrt{3}}\Bigl( S_nD_n+12\frac{S_n^2+D_n^2}{S_nD_n}+\frac{114}{S_nD_n} \Bigr) \end{aligned} $$
Step5：グレブナー基底を用いて変数を消去し、Step6に従って整理して次を得る：
$$ \begin{aligned} a_{n+1}&=\frac{a_n}{4}+\frac{3a_n+12}{4b_n^2}\\ b_{n+1}&=\frac{b_4}{4}+\frac{a_n+7}{4b_n} \end{aligned} $$
Step7：基底の初項を決定する。$S_1=4\sqrt{ 2 },D_1=2\sqrt{ 6 }$ と設定し、$a_1=10,b_1=4$ を得る。
これで、比較的複雑な連立漸化式数列が得られました：

おめでとうございます。これで第2回通項杯の第15問の作問方法を習得しました。解答がどうなるかについては、読者への練習問題として残しておきます。

代数曲線上の変換

さて、商空間の $S_n$ や $C_n$ などの群を変更する方法を学んだところで、今度は基底空間 $\mathbb{A}^n$ を捨てる試みを始めてみましょう。例えば、代数曲面の空間上で変換を行うことを試みます。
次のような代数曲面を考えてみましょう：
$$ \begin{aligned} x^2+y^2+z^2-Cxyz&=K\\ F_{C,K}(x,y,z):=x^2+y^2+z^2-Cxyz-K&=0\\ \end{aligned} $$
ここで $K$ は定数です。次のように変形します：
$$ \begin{aligned} C=I(x,y,z)=\frac{x^2+y^2+y^2-K}{xyz} \end{aligned} $$
次に、$(x,y,z)$ の状態から $(y,z,w)$ の状態へのスライディングウィンドウ（スライド窓）を設定したいと思います。これは次のように対応します：
$$ \begin{aligned} I(x,y,z)&=-I(y,z,w)\\ F_{-C,K}(y,z,w)&=0 \end{aligned} $$
$F_{-C,K}(y,z,w)=0$ を展開すると次が得られます：
$$ \begin{aligned} y^2+z^2+w^2+Cyzw-K&=0\\ w^2+Cyzw+(y^2+z^2-K)=0 \end{aligned} $$
一方、$(x,y,z)$ は $F_{C,K}$ において次を与えます：
$$ y^2+z^2-K=-x^2+Cxyz $$
これを代入すると、
$$ w^2+Cyzw-x^2+Cxzy=(x+w)(w-x+Cyz)=0 $$
一般的な簡単な問題であれば平方根を選びますが、ここは「通項杯」ですので、$w=x-Cyz$ を選択します。このとき次が得られます：
$$ C=\frac{x-w}{yz} $$
これを $x^2+y^2+z^2-Cxyz=K$ に代入して戻すと、
$$ x^2+y^2+z^2-\frac{x-w}{yz}xyz=y^2+z^2+xw=K $$
したがって、
$$ y^2+z^2+xw=yu+z^2+w^2\Rightarrow y^2+xw=w^2+yu $$
さらに、添字 $(x_n,x_{n+1},x_{n+2},x_{n+3},x_{n+4})$ を状態 $(x,y,z,w,u)$ に順次代入すると、漸化式が得られます：
$$ x_{n+2}^2+x_{n}x_{n+3}=x_{n+3}^2+x_{n+1}x_{n+4} $$
このとき、$a_n=\frac{x_{n+1}}{x_n}$ と置けば、次の式が得られます：
$$ a_{n+3}+a_{n+2}a_{n+1}=\frac{1}{a_{n+2}a_{n+1}}+\frac{1}{a_n} $$
ここで $x_1=x_2=1$ を与えて定数 $K$ を確定させるだけで、新しい問題が得られます：

解： $a_{n}=\frac{x_{n+1}}{x_n},x_1=1$ と置くと、容易に次が導かれます：
$$ \begin{aligned} x_nx_{n+3}+x_{n+1}^2+x_{n+2}^2=K&=\frac{16}{9}\\ C_0=\frac{x_1^2+x_2^2+x_3^2-K}{x_1x_2x_3}&=\frac{3}{2} \end{aligned} $$
$I(y,z,w)=-I(x,y,z)$ より $C_n=(-1)^{n-1}C_0=(-1)^{n-1}\frac{3}{2}$ を得て、このとき
$$ x_n^2+x_{n+1}^2+x_{n+2}^2-C_nx_nx_{n+1}x_{n+2}=K,\qquad (K=\frac{16}{9},C_n=\pm\frac{3}{2}) $$
振動する $C_n$ を安定させるために $\hat{x}_n=(-1)^nx_n$ と置くと、次が得られます：
$$ \hat{x}_n^2+\hat{x}_{n+1}^2+\hat{x}_{n+2}^2-\frac{3}{2}\hat{x}_n\hat{x}_{n+1}\hat{x}_{n+2}=\frac{16}{9} $$
最後に $X_n=\frac{C_0}{2}\hat{x}_n=\frac{3}{4}(-1)^nx_n$ と置けば、次が得られます：
$$ X_n^2+X_{n+1}^2+X_{n+2}^2-2X_nX_{n+1}X_{n+2}=1 $$
このとき、この曲面における基本恒等式は次のようになります：
$$ \cos^2A+\cos^2B+\cos^2(A+B)-2\cos A\cos B\cos(A+B)=1 $$
$(X_n,X_{n+1},X_{n+2})=(\cos \theta_{n},\cos \theta_{n+1},\cos(\theta_{n}+\theta_{n+1}))$ と置くと、$X_{n+3}=2X_{n+2}X_{n+1}-X_n$ より次が保証されます：
$$ \begin{aligned} 2\cos\theta_{n+1}\theta_{n+2}&=\cos(\theta_{n+2}+\theta_{n+1})+\cos(\theta_{n+2}-\theta_{n+1})\\ \cos\theta_{n+3}&=\cos(\theta_{n+2}+\theta_{n+1}) \end{aligned} $$
したがって $\theta_{n+3}=\theta_{n+2}+\theta_{n+1}$ となり、直ちに次が得られます：
$$ X_n=\cos\theta_n=\cos(F_{n-2}\theta_1+F_{n-1}\theta_2) $$
これにより、一般項は次のようになります：
$$ \begin{aligned} x_n&=\frac{4}{3}(-1)^{n+F_{n-2}}\cos\Bigl(F_n\arccos\frac{3}{4}\Bigr)\\ a_n&=(-1)^{F_n+1}\frac{\cos(F_{n+1}\arccos\frac{3}{4})}{\cos(F_n\arccos\frac{3}{4})} \end{aligned} $$
ここで、$F_n$ はフィボナッチ数列であり、$F_0=0,F_1=1$ です。
ここまで来ると、第2回通項杯で最も難易度が高い第13問をすでに作問（解答）していることに気づくでしょう。
もし指定したスライディングウィンドウが $I(x,y,z)=-I(y,z,w)$ ではなく $I(x,y,z)=I(y,z,w)$ であれば、以下のような類似の問題が得られます：

この種の問題も、依然として以下の方法で生成することができます：
Step1：マルコフ曲面（Markov surface）を選択する
$$ F_{t,K}(x,y,z)=x^2+y^2+z^2+\lambda(xy+yz+zx)+\nu-txyz-K=0 $$
Step2：曲面パラメータ関数を定義する
$$ t=I(x,y,z)=\frac{x^2+y^2+z^2+\lambda(xy+yz+zx)+\mu-K}{xyz} $$
Step3：スライディングウィンドウの規則を選定する
メビウス変換を選択します：
$$ \phi(t)=\frac{at+b}{ct+d},\qquad(ad-bc\neq0) $$
以下の規則を満たすようにウィンドウのスライドを定めます：
$$ I(x_{n+1},x_{n+2},x_{n+3})=\phi(I(x_n,x_{n+1},x_{n+2})) $$
$t_n:=I(x_n,x_{n+1},x_{n+2})$ と記すと、このとき $t_{n+1}=\phi(t_n)$ となります。
Step4：推移（発展）後の点を曲面上に位置させる
次のように置きます：
$$ (x,y,z,w)=(x_{n},x_{n+1},x_{n+2},x_{n+3}),\qquad t=t_n $$
$F_{\phi(t),K}=(y,z,w)=0$ を要求すると、このとき $w$ に関する二次方程式が必然的に得られます：
$$ w^2+(\lambda(y+z)-\phi(t)yz)w+(y^2+z^2+\lambda yz+\nu -K)=0 $$
Step5：自明な根 $(w-L)$ を分離する
まず根の形式を確定させます：
$$ L(x,y,z)=\alpha x+\beta(y+z)+\gamma yz $$
$w=L$ を二次方程式に代入して戻し、$F_{t,K}(x,y,z)=0$ と置いて定数 $K$ を消去すると、次が得られます：
$$ R(x,y,z,t)=F_{\phi(t),K}(y,z,L)\Bigr|_{K=\ldots} $$
このとき、$R(x,y,z,t)\equiv0$、すなわち恒等的にゼロとなる等式と置くと、これは一つの代数的条件になります。
Step6：解と係数の関係（ビエタの公式）を用いてもう一つの根を求め、漸化式を得た後、変数を消去して不変量（保存量） $K$ を得る：
Step5の時点で、二次方程式には必ず一つの根 $w=L$ が存在します。このとき、もう一つの根を $w$ と置きます（特に明記しない限り、前出のものは $L$ で記述します）。解と係数の関係より、二つの根の和は次のようになります：
$$ w+L=\phi(t)yz-\lambda(y+z) $$
したがって、
$$ w=\phi(t)yz-\lambda(y+z)-L(x,y,z) $$
添字を置き換えることで漸化式が得られます：
$$ x_{n+3}=\phi(t_n)x_{n+1}x_{n+2}-\lambda(x_{n+1}+x_{n+2})-L(x_n,x_{n+1},x_{n+2}) $$
その後、ステップ2で得られた $t_n=I(x_n,x_{n+1},x_{n+2})$ と、二つの根の和・差から得られた $t_n=\cdots$ を連立させて $t_n$ を消去すると、一つの保存量が得られます：
$$ K=\{x_n,x_{n+1},x_{n+2},x_{n+3}\} $$
Step7：$a_n=\frac{x_{n+1}}{x_n}$ と置いて保存量の漸化式を整理し、初期値を与えれば完成です。