レパートリー法（Repertoire Method）で一般解を求めるメモ

#　**目的**
レパートリー法を用いて

```math
\sum_{k=0}^{n} k^2 \tag{0}
```
の一般解を求める．

#　**与えられる式**

```math
\begin{align}
R_0 &=\alpha \tag{1.1} \\
R_n &=R_{n-1}+\beta+n\gamma+n^2\delta \tag{1.2}
\end{align}
```

#　**レパートリー法の解の一般系**
$R_n$の式が次のような式で書けるとして計算をしていく

```math
R_n = A(n)\alpha + B(n)\beta + C(n)\gamma +  D(n)\delta \tag{2}
```

#　**レパートリー法の計算**
## 　具体的な値を入れていく

##　 Rn=1を計算
式1.1から

```math
R_0 = 1 = \alpha
```

式1.2から

```math
\begin{align}
R_n = 1 &= R_{n-1}+\beta+n\gamma+n^2\delta \\
        &= 1 + \beta+n\gamma+n^2\delta \\
      0 &= \beta+n\gamma+n^2\delta
\end{align}
```
よって，$\alpha=1,\beta=0, \gamma = 0, \delta = 0$
このときの$R_n$の値と$\alpha$とかを式(2)に代入して

```math
1 = A(n) \tag{3.1}
```
を得る．

## 　Rn=nを計算
式1.1から

```math
R_0 = 0 = \alpha
```

式1.2から

```math
\begin{align}
R_n = n &= R_{n-1}+\beta+n\gamma+n^2\delta \\
        &= (n-1) + \beta+n\gamma+n^2\delta \\
1 &= \beta+n\gamma+n^2\delta
\end{align}
```
よって，$\alpha=0,\beta=1, \gamma = 0, \delta = 0$

このときの$R_n$の値と$\alpha$とかを式(2)に代入して

```math
n = B(n) \tag{3.2}
```
を得る．

##　Rn=n^2を計算
式1.1から

```math
R_0 = 0 = \alpha
```

式1.2から

```math
\begin{align}
R_n = n^2 &= R_{n-1}+\beta+n\gamma+n^2\delta \\
          &= (n-1)^2 + \beta+n\gamma+n^2\delta \\
          &= n^2 - 2n + 1 + \beta+n\gamma+n^2\delta \\
    2n - 1 &= \beta+n\gamma+n^2\delta 
\end{align}
```
よって，$\alpha=0,\beta=-1, \gamma = 2, \delta = 0$
このときの$R_n$の値と$\alpha$とかを式(2)に代入して

```math
n^2 = -B(n) + 2C(n) \tag{3.3}
```
を得る．

## 　Rn=n^3を計算
式1.1から

```math
R_0 = 0 = \alpha
```

式1.2から

```math
\begin{align}
R_n = n^3 &= R_{n-1}+\beta+n\gamma+n^2\delta \\
          &= (n-1)^3 + \beta+n\gamma+n^2\delta \\
          &= n^3 - 3n^2  + 3n - 1 + \beta+n\gamma+n^2\delta \\
     3n^2 - 3n +1 &= \beta+n\gamma+n^2\delta 
\end{align}
```
よって，$\alpha=0,\beta=1, \gamma = -3, \delta = 3$

このときの$R_n$の値と$\alpha$とかを式(2)に代入して

```math
n^3 = B(n) -3C(n) + 3D(n) \tag{3.4}
```
を得る．

## 　A(n), B(n), C(n), D(n)を求める
上で求めた式

```math
\begin{align}
1 &= A(n) \tag{3.1} \\
n &= B(n) \tag{3.2} \\
n^2 &= -B(n) + 2C(n) \tag{3.3} \\
n^3 &= B(n) -3C(n) + 3D(n) \tag{3.4} \\

\end{align}
```
から残ってる$C(n), D(n)$を求める．

式(3.3)に式(3.2)を代入して$C(n)$を得る．

```math
n^2 = -n + 2C(n) \\
C(n) = \frac{n^2 + n}{2}
```

式(3.4)の$C(n)とB(n)$にこれまで求めた値を代入して$D(n)$を得る．

```math
\begin{align}

n^3 &= n -3(\frac{n^2 + n}{2}) + 3D(n) \\
3D(n) &= n^3 - n + 3(\frac{n^2+n}{2}) \\
D(n) &= \frac{n^3-n}{3} + \frac{n^2+n}{2} \\
 &=\frac{2n^3-2n}{6} + \frac{3n^2+3n}{6} \\
 &= \frac{n(2n^2+3n+1)}{6}
\end{align}
```

```math
= \frac{n(2n+1)(n+1)}{6} \tag{4}
```


#　 **一般解を求める**
式(0)は以下のように表わせる．

```math
S_n = \sum_{k=0}^{n} k^2= \sum_{k=0}^{n-1} k^2 + n^2  = S_{n-1} + n^2
```

ここで$R_n = S_n$として式(1.2)に代入すると，

```math
\begin{align}
R_n &=R_{n-1}+\beta+n\gamma+n^2\delta \\
S_{n-1} + n^2 &= S_{n-1}+\beta+n\gamma+n^2\delta \\
n^2 &= \beta+n\gamma+n^2\delta
\end{align}
```
となり，$\alpha=\beta=\gamma=0,\delta = 1$が得られる．
得られた値を式(2)に代入すると，

```math
\begin{align}
R_n &= A(n)*0 + B(n)*0 + C(n)*0 +  D(n)*1 \\
    &= D(n)
\end{align}
```
となる．
$D(n)$は式(4)より，$\frac{n(2n+1)(n+1)}{6}$であるから，

```math
\sum_{k=0}^{n} k^2 
```
の一般解$R_n$は,

```math
R_n = \frac{n(2n+1)(n+1)}{6}
```
である．

#　参考

* [http://ishare.iask.sina.com.cn/f/36052113.html](http://ishare.iask.sina.com.cn/f/36052113.html)
* [https://blog.wakatta.jp/blog/2012/01/14/concrete-mathematics-repertoire-method/](https://blog.wakatta.jp/blog/2012/01/14/concrete-mathematics-repertoire-method/)
* [https://math.stackexchange.com/questions/67939/repertoire-method-clarification-required-concrete-mathematics](https://math.stackexchange.com/questions/67939/repertoire-method-clarification-required-concrete-mathematics)