4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Posted at

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

\sum_{k=0}^{n} k^2 \tag{0}

の一般解を求める.

# 与えられる式

\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$の式が次のような式で書けるとして計算をしていく

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

# レパートリー法の計算

 具体的な値を入れていく

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

R_0 = 1 = \alpha

式1.2から

\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)に代入して

1 = A(n) \tag{3.1}

を得る.

 Rn=nを計算

式1.1から

R_0 = 0 = \alpha

式1.2から

\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)に代入して

n = B(n) \tag{3.2}

を得る.

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

R_0 = 0 = \alpha

式1.2から

\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)に代入して

n^2 = -B(n) + 2C(n) \tag{3.3}

を得る.

 Rn=n^3を計算

式1.1から

R_0 = 0 = \alpha

式1.2から

\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)に代入して

n^3 = B(n) -3C(n) + 3D(n) \tag{3.4}

を得る.

 A(n), B(n), C(n), D(n)を求める

上で求めた式

\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)$を得る.

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

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

\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}
= \frac{n(2n+1)(n+1)}{6} \tag{4}

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

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)に代入すると,

\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)に代入すると,

\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}$であるから,

\sum_{k=0}^{n} k^2 

の一般解$R_n$は,

R_n = \frac{n(2n+1)(n+1)}{6}

である.

# 参考

4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?