公式解説では漸化式をもとに \(O(N)\) 時間で \(C _ N\) の値を求めていました。 この漸化式を変形していくことでも、\(C _ N\) の値を閉じた式の形で求めることができます。

\[C _ N=-1+\dfrac{N-3}{N-1}C _ {N-1}\]の両辺に \((N-1)(N-2)\) をかけて \[(N-1)(N-2)C _ N=-(N-1)(N-2)+(N-2)(N-3)C _ {N-1}\] を得ます。 両辺に \(\dfrac{N(N-1)(N-2)}3\) を加えて \[(N-1)(N-2)C _ N+\dfrac{N(N-1)(N-2)}3=(N-2)(N-3)C _ {N-1}+\dfrac{(N-1)(N-2)(N-3)}3\] を得、これを整理して \[(N-1)(N-2)\!\left(C _ N+\dfrac{N}3\right)=(N-2)(N-3)\!\left(C _ {N-1}+\dfrac{N-1}3\right)\] となります。

ここから \((N-1)(N-2)\!\left(C _ N+\dfrac{N}3\right)\) の値が \(N\) によらない定数となることがわかります。 \(C _ 1=0\) から \(N=1\) を代入してこの値が \(0\) であることがわかるため、\(N\gt2\) なら \(C _ N=-\dfrac{N}3\) が示せます。

\(C _ 2\) は漸化式に従って \(-1\) と求められるので、これで公式解説の別解と同じ結果が得られました。