階段の昇り方の個数をsympyで一般化することで二項係数の和の公式を作る

背景 ～パスカルの三角形とフィボナッチ数列の関係～

パスカルの三角形に関して，以下のような有名な性質があります。

パスカルの三角形を斜めに切って和を取るとフィボナッチ数列が現れる

帰納的証明

フィボナッチ数列もパスカルの三角形も，ともに帰納的に定義されているものなので，帰納的な証明が自然でしょう。実際，パスカルの三角形の作られ方を見れば，「前2段の和が次の段になっている」ことはほぼ明らかでありましょう。（偶奇の違いによって末端の1の現れ方が異なる点は注意が必要ですが。）

対応付けによる理解

階段の昇り方の個数

一方，結論にフィボナッチ数列が現れる有名な問題として，次のような階段の昇り方の個数問題があります。

1歩で1段または2段のいずれかで階段を昇るとき，n段の階段の昇り方は何通りあるか。

漸化式による数え上げ

$n$段の階段の昇り方の総数を$F_n$とおくと，$F_1=1$，$F_2=2$であり，「ゴール寸前にどこにいたか」で場合分けすると，漸化式
$$ F_{n}=F_{n-1}+F_{n-2} \quad (n\geqq2)$$
が成り立つことが直ちに分かります。よって，これは次のようなフィボナッチ数列をなすことが分かります。

$n$	1	2	3	4	5	6	7	8	9
$F_n$	1	2	3	5	8	13	21	34	55

場合分けによる数え上げ

一方，この昇り方を，「2段昇り」を何度用いるかによって場合分けして求めようとしたとします。「2段昇り」を$k$回 $\left(0\leqq k\leqq \left[\frac{n}{2}\right]\right)$ 使うとすると，「1段昇り」は$n-2k$回使うことになります。合計 $(n-2k)+k=n-k$ 回のステップのうち，「2段昇り」$k$ 回の配置の仕方は
${}_{n-k} \mathrm{C}_k$通りです。$k$ を $0$ から $\left[\frac{n}{2}\right]$ まで動かしてこの和をとれば，

$$F_n=\displaystyle\sum_{k=0}^{\left[ \frac{n}{2} \right]} {}_{n-k} \mathrm{C}_k $$

となります。

このように，1つの問題を2通りで解いた解法の結果を比較することにより，二項係数の新たな和の公式が得られたことになります。フィボナッチ数列の一般項を与えるビネの公式により，二項係数に関する，次の閉じた和の公式が得られました。

\displaystyle\sum_{k=0}^{\left[ \frac{n}{2} \right]} {}_{n-k} \mathrm{C}_k =
\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right\}

2007京大理系数学(乙)第1問(2)

さて，このような「階段の昇り方の数え上げ問題」の亜種として，次のような問題があります。

1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする。15段の階段を昇る昇り方は何通りあるか。　［2007京大理系数学(乙)第1問(2)］

先程と同様の問題ですが，今度は「2段昇りが連続しない」という制約条件が付いています。

四項間漸化式による数え上げ

$n$段の階段の昇り方の総数を$a_n$とおくと，$a_1=1,\ a_2 = 2,\ a_3=3$です。
$n\geqq 4$のとき，最初の一歩で場合分けします。最初が「1段昇り」のときは残る昇り方は$a_{n-1}$通り。最初が「2段昇り」のときはその直後は必ず「1段昇り」になり，残る昇り方は$a_{n-3}$通り。ゆえに

$$ a_{n}=a_{n-1}+a_{n-3} \quad (n\geqq4)$$

という四項間漸化式が成り立ちます。これを繰り返し用いると，

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$a_n$	1	2	3	4	6	9	13	19	28	41	60	88	129	189	277

となり，求める答 $a_{15}=277$ が得られます。

場合分けによる数え上げ

一方，フィボナッチ数列のときと同様，この昇り方を，「2段昇り」を何度用いるかによって場合分けして求めようとしたとします。「2段昇り」を$k$回 $\left(0\leqq k\leqq \left[\frac{n}{2}\right]\right)$ 使うとすると，「1段昇り」は$n-2k$回使うことになります。合計 $(n-2k)+k=n-k$ 回のステップのうち，「2段昇り」$k$ 回を配置することになります。ただし「2段昇りは連続しない」という制約条件があるので，「$n-2k$個の1と$k$個の2を，2が連続せぬよう並べる個数」を求めることになります。これは，$n-2k$個の1がなす$n-2k+1$個のすき間（両端含む）に$k$個の2を挿入すると考えれば，$\displaystyle_{n-2k+1}\mathrm{C}_{k}$通りとなります。（ただし，$n-2k+1\geqq k$でなければならないので，$0\leqq k\leqq \left[\frac{n+1}{3}\right]$ が$k$の変域となります。）

よって，

$$ a_n = \displaystyle\sum_{k=0}^{[(n+1)/3]}\displaystyle_{n-2k+1}\mathrm{C}_{k} $$

が求める個数となります。$n=15$の場合，

a_{15} = \displaystyle_{16}\mathrm{C}_{0} + \displaystyle_{14}\mathrm{C}_{1} + \displaystyle_{12}\mathrm{C}_{2} + \displaystyle_{10}\mathrm{C}_{3} + \displaystyle_{8}\mathrm{C}_{4} + \displaystyle_{6}\mathrm{C}_{5} = 277

となります。

一般化して新たな二項係数の和の公式を作ろう！

この2つの解法を比較することで，また二項係数に関する新たな和の公式が得られそうです。$n$を1つずらせば，

\displaystyle\sum_{k=0}^{\left[\frac{n}{3}\right]}\displaystyle_{n-2k}\mathrm{C}_{k} = a_{n}

ただし{$a_n$}は $a_0=a_1=a_2=1,\ a_{n}=a_{n-1}+a_{n-3} \quad (n\geqq3)$ で定まる数列

という新たな和の公式が得られたことになります。

一般項を閉じた形で求めたい

四項間漸化式で定義された数列{$a_n$}の一般項を求めるため，この漸化式の特性方程式

x^3-x^2-1=0

を解くことを考えます。これは普通には解けないため，三次方程式の解の公式を与えるカルダノの解法に従って解いていきましょう。

立方完成

まず，$y=x-\frac13$と変数変換することで立方完成すると，解くべき方程式は

y^3-\frac13y-\frac{29}{27}=0

となります。

因数分解

ここで，

\begin{cases}
\alpha^3+\beta^3=-\frac{29}{27}\\
\alpha^3\beta^3 = \frac19
\end{cases}

を満たす複素数$\alpha,\beta$が見つかったとすると，解くべき方程式は

y^3+\alpha^3+\beta^3-3y\alpha\beta=0

となり，これは1の3乗根$\omega$を用いて

(y+\alpha+\beta)(y+\omega \alpha + \omega^2\beta)(y+\omega^2 \alpha + \omega\beta)=0

と因数分解できるため，解は

y= - (\alpha+\beta) ,\  {-(\omega \alpha + \omega^2\beta)},\  {-(\omega^2 \alpha + \omega\beta)}

と求められ，当初の特性方程式の解は

x= \frac13- (\alpha+\beta) ,\ \ \frac13-(\omega \alpha + \omega^2\beta),\ \ \frac13-(\omega^2 \alpha + \omega\beta)

と求められることになります。

α, β を求める

解と係数の関係により，$\alpha^3$と$\beta^3$は$t$に関する2次方程式

t^2 + \frac{29}{27} t+ \frac19=0

の2解であるため，

-\frac{29\pm3\sqrt{93}}{54}

と求められます。ゆえに，

\begin{cases}
A = \left(\frac{29-3\sqrt{93}}{54}\right)^{1/3} \\
B = \left(\frac{29+3\sqrt{93}}{54}\right)^{1/3} \\
\end{cases}

とおけば，当初の特性方程式の解は

x= \frac13+A+B ,\ \ \frac13+\omega A + \omega^2B,\ \ \frac13+\omega^2 A + \omega B

と表せたことになります。

数列の一般項

以上より，漸化式 $a_{n}=a_{n-1}+a_{n-3} \quad (n\geqq3)$ で定まる数列 {$a_n$} の一般項は

a_n = p\left(\frac13+A+B\right)^n + q\left(\frac13+\omega A + \omega^2B\right)^n+r\left( \frac13+\omega^2 A + \omega B\right)^n

で表されることが分かりました。ただし $p, q, r$は初項に応じて決まる複素数定数のパラメータです。

初項に応じたパラメータの決定

今回の初項 $a_0=a_1=a_2=1$ に呼応するパラメータ $p, q, r$ を決定しましょう。この先は手計算でやる気が起きないので，sympyの力を借ります。

今回は Google Colab でノートブックを作ってみましょう。

まずは sympy をインポートし，MathJaxによる綺麗な画面出力が得られるように設定します。

from sympy import *
init_printing()

注意点として，三乗根を計算するときに **(1/3) としてしまうと，1/3 の部分で浮動小数点演算が行われてしまい，0.3333... という近似値になってしまいます。有理数として厳密な計算をしてほしいので，Rational(1,3) と書く必要があります。この分数が何度も出てくるので，それを frac13 という変数にしてしまいましょう。そして，先程のA，Bを定義します。

frac13 = Rational(1,3)
A = ((29-3*sqrt(93))/54)**frac13
B = ((29+3*sqrt(93))/54)**frac13

また，1の三乗根$\omega$を変数wとして定義します。これは，$\omega = e^{\frac23\pi i}$と考えて

w = exp(2*frac13*pi*I)

と定義してもいいですし，単に

w = (-1)**(2*frac13)

としても同じになります。

現時点で A, B, w を確認しておきましょう。

display(A)
display(B)
display(w)

\begin{align*}
\sqrt[3]{\frac{29}{54} - \frac{\sqrt{93}}{18}}\\
\sqrt[3]{\frac{\sqrt{93}}{18} + \frac{29}{54}}\\
\left(-1\right)^{\frac{2}{3}}
\end{align*}

次に，$p,q,r$を文字扱いした上で，$a_n$の一般項を定義します。

p,q,r = symbols('p q r')

def a(n):
  return p*(frac13+A+B)**n + q*(frac13+w*A+w*w*B)**n + r*(frac13+w*w*A+w*B)**n

連立方程式を立てる

$p,q,r$についての連立方程式

a(0)=a(1)=a(2)=1

を解いて，これを満たす$(p,q,r)$を求めたいわけです。この連立方程式をsympyで解くには，solve を用いて

solve([a(0)-1, a(1)-1, a(2)-1], [p,q,r])

とすればよいわけですが，係数があまりにも複雑なためか，ただの三元一次連立方程式の割に，計算が遅すぎていつまで待っても答が求まりません。

連立方程式を行列表示する

そこで，まずはこの連立方程式を行列表示しましょう。そのために，係数行列を取り出します。先にそれぞれの式を simplify しておきます。

a0, a1, a2 = map(simplify, [a(0), a(1), a(2)])
display(a0)
display(a1)
display(a2)

\begin{align*}
p + q + r\\
\frac{p \left(2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2 + 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}\right)}{6} + \frac{q \left(2 - 2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}\right)}{6} + \frac{r \left(2 - 2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}\right)}{6}\\
\frac{p \left(2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2 + 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}\right)^{2}}{36} + \frac{q \left(2 - \sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}\right)^{2}}{36} + \frac{r \left(2 - \sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}\right)^{2}}{36}
\end{align*}

それぞれの式の$p,q,r$の係数を取り出して並べ，係数行列を作ります。

M = Matrix([[a0.coeff(p),a0.coeff(q),a0.coeff(r)], [a1.coeff(p),a1.coeff(q),a1.coeff(r)],[a2.coeff(p),a2.coeff(q),a2.coeff(r)]])
display(M)

\left[\begin{matrix}1 & 1 & 1\\\frac{2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{6} + \frac{1}{3} + \frac{2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{6} & \frac{1}{3} - \frac{2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}}}{6} + \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{6} & \frac{1}{3} - \frac{2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}}}{6} + \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{6}\\\frac{\left(2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2 + 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}\right)^{2}}{36} & \frac{\left(2 - \sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}\right)^{2}}{36} & \frac{\left(2 - \sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}\right)^{2}}{36}\end{matrix}\right]

解くべき連立方程式は

M\begin{pmatrix}p \\ q \\ r \end{pmatrix}=\begin{pmatrix}1 \\ 1 \\ 1 \end{pmatrix}

なのであるから，逆行列$M^{-1}$を求められれば，

\begin{pmatrix}p \\ q \\ r \end{pmatrix}= M^{-1}\begin{pmatrix}1 \\ 1 \\ 1 \end{pmatrix}

として$p, q, r$が定まることになります。

しかし，sympyで

M.inv()

としても，やはり成分が複雑すぎて，いつまで経っても逆行列の計算は終わりません。そこで，別の方法を考えます。

逆行列を余因子行列経由で求める

行列式を求めるために

detM = simplify(M.det())
display(detM)

としてみると，

\frac{\sqrt[3]{-1} \sqrt{93} \left(1 + \sqrt[3]{-1}\right)}{3}

と，意外とスッキリとした結果になる点に注目します。そこで，adjugate() メソッドで余因子行列$\tilde A$を求めてみましょう。

adjM = simplify(M.adjugate())
display(adjM)

\left[\begin{matrix}- \frac{\sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{54} - \frac{\sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{54} - \frac{\left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{27} - \frac{\sqrt[3]{-29 + 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{27} - \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{54} - \frac{2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}}}{54} + \frac{\sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{54} + \frac{\sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}}}{54} + \frac{\left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{27} + \frac{\sqrt[3]{-29 - 3 \sqrt{93}} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{27} + \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{54} + \frac{2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}}}{54} + \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93}}{9} + \frac{\sqrt[3]{-1} \sqrt{93}}{9} & - \frac{2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}}}{9} - \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{9} - \frac{\sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{18} - \frac{\sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}}}{18} + \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{9} + \frac{2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}}}{9} + \frac{\sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{18} + \frac{\sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{18} & - \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{6} - \frac{\sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{6} + \frac{\sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{6} + \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{6}\\- \frac{\sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{27} - \frac{\left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{27} + \frac{\sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{54} + \frac{2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{54} + \frac{2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{54} + \frac{\sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{54} - \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{54} - \frac{\sqrt[3]{-29 - 3 \sqrt{93}} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{27} - \frac{\sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}}}{54} + \frac{2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}}}{54} + \frac{\left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{27} + \frac{\sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{54} + \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93}}{9} + \frac{\sqrt[3]{-1} \sqrt{93}}{9} & - \frac{\sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{18} - \frac{2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{9} - \frac{2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{9} - \frac{\sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{18} - \frac{\sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{18} - \frac{\sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{9} + \frac{\left(-1\right)^{\frac{2}{3}} \sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{18} + \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{9} & \frac{2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{6} + \frac{2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{6} - \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{6} + \frac{2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}}}{6}\\- \frac{\sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{54} - \frac{2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{54} - \frac{2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{54} - \frac{\sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{54} + \frac{\left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{27} + \frac{\sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{27} - \frac{\sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{54} - \frac{\left(-1\right)^{\frac{2}{3}} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{27} - \frac{\sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{54} + \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{54} + \frac{\sqrt[3]{-1} \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{27} + \frac{\left(-1\right)^{\frac{2}{3}} \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{54} + \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93}}{9} + \frac{\sqrt[3]{-1} \sqrt{93}}{9} & \frac{\sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{18} + \frac{2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{9} + \frac{2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{9} + \frac{\sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}}{18} - \frac{\sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{18} - \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{9} + \frac{\sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}}}{18} + \frac{2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}}}{9} & - \frac{2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{6} - \frac{2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{6} - \frac{\sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}}{6} + \frac{\left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}}}{6}\end{matrix}\right]

結果は激しい感じになりましたが，計算はすぐに終わりました。一般に計算量が多く速度的に不利と言われる余因子行列経由での逆行列の計算の方が速いという，意外な結果となりました。余因子行列ならば，除法を使わず乗法だけで計算できるので，今回のような複雑な係数を含む記号計算の場合，除法を含む掃き出し法などと比べ記号計算が速くなったのではないか，と思われます。

余因子行列と行列式が求まったのだから，逆行列はもう求まったも同然です。

Minv = simplify(adjM/detM)
display(Minv)

\left[\begin{matrix}\frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- 6 \sqrt[3]{-1} \sqrt{93} - 6 \left(-1\right)^{\frac{2}{3}} \sqrt{93} - 2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}} - \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - 2 \sqrt[3]{-29 - 3 \sqrt{93}} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} - 2 \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - \sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} - \sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}} + 2 \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2 \sqrt[3]{-29 + 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} + \sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} + \sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}}\right)}{1674 \left(1 + \sqrt[3]{-1}\right)} & \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- \sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}} - \sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}} - 2 \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + \sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}}\right)}{558 \left(1 + \sqrt[3]{-1}\right)} & \frac{2^{\frac{2}{3}} \sqrt{93} \left(- \sqrt[3]{29 - 3 \sqrt{93}} + \sqrt[3]{3 \sqrt{93} + 29}\right)}{186}\\\frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} - \sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2 \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 6 \sqrt[3]{-1} \sqrt{93} - 6 \left(-1\right)^{\frac{2}{3}} \sqrt{93} - \sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} - 2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}} + \sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \sqrt[3]{-29 - 3 \sqrt{93}} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}\right)}{1674 \left(1 + \sqrt[3]{-1}\right)} & \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(\sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - \sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}} + \sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}\right)}{558 \left(1 + \sqrt[3]{-1}\right)} & \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} - 2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}} + \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29}\right)}{186 \left(1 + \sqrt[3]{-1}\right)}\\\frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- 2 \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 6 \sqrt[3]{-1} \sqrt{93} - 6 \left(-1\right)^{\frac{2}{3}} \sqrt{93} - \sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}} - 2 \sqrt[3]{-29 + 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + \sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}}\right)}{1674 \left(1 + \sqrt[3]{-1}\right)} & \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} - \sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} - 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}} - \sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + \sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}}\right)}{558 \left(1 + \sqrt[3]{-1}\right)} & \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}}\right)}{186 \left(1 + \sqrt[3]{-1}\right)}\end{matrix}\right]

逆行列が求まったので，$(p,q,r)$を求めます。

v = simplify(Minv * Matrix([1,1,1]))

$(p,q,r)=(v[0],v[1],v[2])$ が連立方程式の解となります。

\begin{align*}
p = \frac{- \sqrt{93} \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \cdot 2^{\frac{2}{3}} \sqrt{93} \sqrt[3]{29 - 3 \sqrt{93}} - \sqrt[3]{2} \sqrt{93} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \sqrt{93} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2 \cdot 2^{\frac{2}{3}} \sqrt{93} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{2} \sqrt{93} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} + 279 - \sqrt{93} \sqrt[3]{-29 + 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \cdot 2^{\frac{2}{3}} \sqrt{93} \sqrt[3]{-29 + 3 \sqrt{93}} - \sqrt[3]{-2} \sqrt{93} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \sqrt[3]{-1} \sqrt{93} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2 \sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt{93} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{-2} \sqrt{93} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} + 279 \sqrt[3]{-1}}{837 \left(1 + \sqrt[3]{-1}\right)}
\\
q  = \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + \sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} + \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 3 \sqrt[3]{-1} \sqrt{93} - 3 \left(-1\right)^{\frac{2}{3}} \sqrt{93} - \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} - 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}} - \sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} + \sqrt[3]{-29 - 3 \sqrt{93}} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}\right)}{837 \left(1 + \sqrt[3]{-1}\right)}
\\
r = \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - \sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - 3 \sqrt[3]{-1} \sqrt{93} - 3 \left(-1\right)^{\frac{2}{3}} \sqrt{93} - \sqrt[3]{-29 + 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} - \sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}} + \sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}}\right)}{837 \left(1 + \sqrt[3]{-1}\right)}
\end{align*}

結論：一般項の完成形

これにて一般項の完成形が得られました！

\displaystyle\sum_{k=0}^{\left[\frac{n}{3}\right]}\displaystyle_{n-2k}\mathrm{C}_{k}  = p\left(\frac13+A+B\right)^n + q\left(\frac13+\omega A + \omega^2B\right)^n+r\left( \frac13+\omega^2 A + \omega B\right)^n

ただし$\omega$は1の三乗根であり，また他の文字定数は以下の通り。

\begin{cases}
A=\sqrt[3]{\frac{29}{54} - \frac{\sqrt{93}}{18}}\\
B=\sqrt[3]{\frac{\sqrt{93}}{18} + \frac{29}{54}}\\
p = \frac{- \sqrt{93} \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \cdot 2^{\frac{2}{3}} \sqrt{93} \sqrt[3]{29 - 3 \sqrt{93}} - \sqrt[3]{2} \sqrt{93} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \sqrt{93} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2 \cdot 2^{\frac{2}{3}} \sqrt{93} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{2} \sqrt{93} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} + 279 - \sqrt{93} \sqrt[3]{-29 + 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \cdot 2^{\frac{2}{3}} \sqrt{93} \sqrt[3]{-29 + 3 \sqrt{93}} - \sqrt[3]{-2} \sqrt{93} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \sqrt[3]{-1} \sqrt{93} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2 \sqrt[3]{-1} \cdot 2^{\frac{2}{3}} \sqrt{93} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{-2} \sqrt{93} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} + 279 \sqrt[3]{-1}}{837 \left(1 + \sqrt[3]{-1}\right)}
\\
q  = \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + \sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} + \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 3 \sqrt[3]{-1} \sqrt{93} - 3 \left(-1\right)^{\frac{2}{3}} \sqrt{93} - \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} - 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{-29 + 3 \sqrt{93}} - \sqrt[3]{2} \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} + \sqrt[3]{-29 - 3 \sqrt{93}} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \left(-2\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + \sqrt[3]{-2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}}\right)}{837 \left(1 + \sqrt[3]{-1}\right)}
\\
r = \frac{\left(-1\right)^{\frac{2}{3}} \sqrt{93} \left(- \sqrt[3]{2} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - \sqrt[3]{29 - 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - \sqrt[3]{2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} - 3 \sqrt[3]{-1} \sqrt{93} - 3 \left(-1\right)^{\frac{2}{3}} \sqrt{93} - \sqrt[3]{-29 + 3 \sqrt{93}} \left(3 \sqrt{93} + 29\right)^{\frac{2}{3}} - 2 \left(-2\right)^{\frac{2}{3}} \sqrt[3]{29 - 3 \sqrt{93}} - \sqrt[3]{-2} \left(29 - 3 \sqrt{93}\right)^{\frac{2}{3}} + \left(-29 + 3 \sqrt{93}\right)^{\frac{2}{3}} \sqrt[3]{3 \sqrt{93} + 29} + 2 \cdot 2^{\frac{2}{3}} \sqrt[3]{-29 - 3 \sqrt{93}} + \sqrt[3]{2} \left(-29 - 3 \sqrt{93}\right)^{\frac{2}{3}}\right)}{837 \left(1 + \sqrt[3]{-1}\right)}
\end{cases}

確認

この一般項が正しいかどうか，念のため確認してみましょう。

$a_n$の一般項の表式において，$(p,q,r)$のところに$(v[0],v[1],v[2])$を代入したものを$b_n$と定義することにします。代入は subs() メソッドで行えます。代入後の簡約化操作 simplify も込めておきます。

def b(n):
  return simplify(a(n).subs([(p, v[0]), (q, v[1]), (r, v[2])]))

これで小さな n の値に対する値を算出させてみます。

[b(n) for n in range(20)]

[1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872]

となり，先程漸化式を手動で繰り返し計算したときと同じ数列が得られていることが分かります。これで，この一般項の妥当性が検証できました！

Google Colab リンク

最後に，この記事を書くために実際に自分が使った Google Colab のノートブックを公開しておきます。ご参考まで。