\displaylines{
a = \{1,3,7,15,\cdots\}\\
a_{n+1} = 2 \cdot a_n + 1 \quad (a_1 = 1)}
このような漸化式があったとします。受験数学では良くみる形ですね。
これは、以下の形で一般項を求めることができます。
a_n = 2^n - 1
つまり、ほぼ $a_n = 2^n$ です。$2^n$ だったらわかりやすいのに、この定数項は何なのか？
アフィン変換
ちなみに、この漸化式は数直線上のアフィン変換であると考えられます。定数項のために余剰次元を用意すると、このアフィン変換はジョルダン分解を施すことにより、以下のように整理できます。
\displaylines{
\begin{pmatrix}
a_{n+1} \\
1
\end{pmatrix}=\begin{pmatrix}
2 & 1 \\
0 & 1
\end{pmatrix}\begin{pmatrix}
a_{n} \\
1
\end{pmatrix}\\
=\begin{pmatrix}
-1 & 1 \\
1 & 0
\end{pmatrix}\begin{pmatrix}
1 & 0 \\
0 & 2
\end{pmatrix}\begin{pmatrix}
0 & 1 \\
1 & 1
\end{pmatrix}\begin{pmatrix}
a_{n} \\
1
\end{pmatrix}\\
\Longleftrightarrow\\
\begin{pmatrix}
a_n \\
1
\end{pmatrix}
=\begin{pmatrix}
-1 & 1 \\
1 & 0
\end{pmatrix}\begin{pmatrix}
1 & 0 \\
0 & 2
\end{pmatrix}^{n-1}\begin{pmatrix}
0 & 1 \\
1 & 1
\end{pmatrix}\begin{pmatrix}
a_{1} \\
1
\end{pmatrix}\\
\Longleftrightarrow\\
a_{n}=\begin{pmatrix}
-1 & 1
\end{pmatrix}\begin{pmatrix}
1 & 0 \\
0 & 2^{n-1}
\end{pmatrix}\begin{pmatrix}
1 \\
a_{1}+1
\end{pmatrix}\\
= 2^n - 1
}
2進数
もうひとつの考え方を紹介します。$a_{n+1} = 2 \cdot a_n + 1 \quad (a_1 = 1)$ という漸化式は以下のような遷移を辿ります。
\displaylines{
a_1 = 1\\
a_2 = 2\cdot(1) + 1 = 2^1 + 1\\
a_3 = 2\cdot(2^1 + 1) + 1 = 2^2 + 2^1 + 1\\
\vdots
}
これは、$2$ 進数で考えると以下のようになります。
\displaylines{
a_1 = (\cdots0001)_2\\
a_2 = (\cdots0011)_2\\
a_3 = (\cdots0111)_2\\
\vdots
}
つまり、$a_n$ は、$2$ 進数において $n$ 個 $1$ を並べた数です。これに $1$ を足せば、すべての桁が繰り上がって $2^n$ になります。よって、$a_n = 2^n - 1$ です。
他の進法では
同様に考えれば、例えば
\displaylines{
b_n = \{2,8,26,\cdots\}\\
b_{n+1} = 3 \cdot b_n + 2\quad (b_1 = 2)\\
}
が、
\displaylines{
b_1 = (\cdots0002)_3\\
b_2 = (\cdots0022)_3\\
b_3 = (\cdots0222)_3\\
\vdots
}
となり、よって $b_n = 3^n-1$ となることも理解しやすいと思います。
一般に、次のことが言えます。
-
$p$ 進数において $p^n - 1$ は、$n$ 個の $p-1$ を並べた数になる
一般漸化式
ここで、次のような疑問が出てきます。
一般漸化式 $f_{n+1} = p \cdot f_n + q$ の一般項を求められないか？
そこで、アフィン変換を用いて力押しで一般項を求めてみます。
\displaylines{
\begin{pmatrix}
f_{n+1} \\
1
\end{pmatrix}=\begin{pmatrix}
p & q \\
0 & 1
\end{pmatrix}\begin{pmatrix}
f_{n} \\
1
\end{pmatrix}\\
=\begin{pmatrix}
-\frac{q}{p-1} & 1 \\
1 & 0
\end{pmatrix}\begin{pmatrix}
1 & 0 \\
0 & p
\end{pmatrix}\begin{pmatrix}
0 & 1 \\
1 & \frac{q}{p-1}
\end{pmatrix}\begin{pmatrix}
f_n \\
1
\end{pmatrix}\\}
$\frac{q}{p-1}$ が煩雑なので、$\gamma$ と定義します。
\displaylines{
\begin{pmatrix}
f_{n+1} \\
1
\end{pmatrix}
=\begin{pmatrix}
-\gamma & 1\\
1 & 0
\end{pmatrix}\begin{pmatrix}
1 & 0 \\
0 & p
\end{pmatrix}\begin{pmatrix}
0 & 1 \\
1 & \gamma
\end{pmatrix}\begin{pmatrix}
f_n \\
1
\end{pmatrix}\\
\Longleftrightarrow\\
f_n= (f_1 + \gamma)\cdot p^{n-1} - \gamma \qquad (\gamma = \frac{q}{p-1})
}
これが一般項となります。
p進数
これを $p$ 進数として考えると、少し面白いことがわかってきます。$f_{n+1} = p \cdot f_n + q$ の遷移を考えます。
f_1 = (\cdots 0000f_1)_p
$p$ 進数では、$p$ をかけることは左にシフトさせることなので、$f_{n+1}$ は $f_n$ を左にシフトした上で $q$ を足した数になります。
\displaylines{
f_2 = (\cdots 000f_1 q)_p\\
f_3 = (\cdots 00f_1 qq)_p\\
f_4 = (\cdots 0f_1 qqq)_p\\
\vdots
}
つまり、$f_n = (\cdots 00f_1qq\cdots qq)_p$（$q$ は $n-1$ 個連続）です。
これは、$f_n = (\cdots 00f_100\cdots00)_p + (\cdots 000qq \cdots qq)_p$ に分けて考えられます。
左側
$(\cdots 00f_100\cdots00)_p$ は、$f_1$ を左に $n-1$ 回シフトしたものなので、$f_1 \cdot p^{n-1}$ です。
右側
$(\cdots 000qq\cdots qq)_p$ は、$q \times (\cdots 00011\cdots11)_p$ と考えることができます。
では、$(\cdots 00011\cdots11)_p$ はどうやって求めるのか。
ここで、
- $p$ 進数において $p^n - 1$ は、$n$ 個の $p-1$ を並べた数になる
ことを思い出すと、$(\cdots00011\cdots11)_p = \frac{1}{p-1}(p^{n-1}-1)$ です。
$p^n - 1 = (p - 1)(p^{n-1} + p^{n-2} + \cdots + p + 1)$ は因数分解の問題では頻出する形ですが、このように $p$ 進数で考えると理解しやすいかもです。
合計
以上の議論をまとめると、
\displaylines{
f_n = f_1 \cdot p^{n-1} + q \cdot \frac{1}{p-1}(p^{n-1}-1) \\
= f_1 \cdot p^{n-1} + \gamma \cdot (p^{n-1}-1)\\
= (f_1 + \gamma) \cdot p^{n-1} - \gamma \qquad (\gamma = \frac{q}{p-1})
}
となり、$p$ 進数として考えても一般項を求められることがわかります。