漸化式は数直線上のアフィン変換であり、p進数だと考えやすい

```math
\displaylines{
a = \{1,3,7,15,\cdots\}\\
a_{n+1} = 2 \cdot a_n + 1 \quad (a_1 = 1)}
```

　このような漸化式があったとします。受験数学では良くみる形ですね。

 　これは、以下の形で一般項を求めることができます。

  ```math
  a_n = 2^n - 1
  ```

  　つまり、ほぼ $a_n = 2^n$ です。$2^n$ だったらわかりやすいのに、この定数項は何なのか？

# アフィン変換

   　ちなみに、この漸化式は数直線上のアフィン変換であると考えられます。定数項のために余剰次元を用意すると、このアフィン変換はジョルダン分解を施すことにより、以下のように整理できます。

```math
\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)$ という漸化式は以下のような遷移を辿ります。

 ```math
 \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$ 進数で考えると以下のようになります。

 ```math
 \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$ です。

 ## 他の進法では

 　同様に考えれば、例えば

  ```math
  \displaylines{
  b_n = \{2,8,26,\cdots\}\\
  b_{n+1} = 3 \cdot b_n + 2\quad (b_1 = 2)\\
  }
 ```

 　が、
  
 ```math
 \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$ の一般項を求められないか？** 

   そこで、アフィン変換を用いて力押しで一般項を求めてみます。

```math
\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$ と定義します。

```math
\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$ の遷移を考えます。

 ```math
 f_1 = (\cdots 0000f_1)_p
 ```

 　$p$ 進数では、$p$ をかけることは左にシフトさせることなので、$f_{n+1}$ は $f_n$ を左にシフトした上で $q$ を足した数になります。

```math
\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)$ です。


:::note info

$p^n - 1 = (p - 1)(p^{n-1} + p^{n-2} + \cdots + p + 1)$ は因数分解の問題では頻出する形ですが、このように $p$ 進数で考えると理解しやすいかもです。
:::

## 合計

   　以上の議論をまとめると、

```math
\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$ 進数として考えても一般項を求められることがわかります。