連立漸化式
連立漸化式
初期条件 $a_1 = a,$ $b_1 = b$ と連立漸化式
\[ a_{n+1} = pa_n+qb_n, \quad b_{n+1} = ra_n+sb_n \quad (ps \neq qr)\]
で定まる数列 $\{ a_n\},$ $\{ b_n\}$ の一般項は,
- $\{ a_n+kb_n\}$ が等比数列になるような定数 $k$ を見つける方法
- $\{ a_n\}$ の $3$ 項間漸化式に帰着させる方法
定理《連立 $2$ 項間線形漸化式》
$p,$ $q,$ $r,$ $s$ ($p,$ $r$ は $0$ でも $1$ でもなく, $ps-qr \neq 0$) を定数とする.
$a_1,$ $b_1$ の値と
\[\left\{\begin{array}{l}
a_{n+1} = pa_n+qb_n \quad \cdots [\sharp ], \\
b_{n+1} = ra_n+sb_n \quad \cdots [\flat ]
\end{array}\right.\]
で定まる数列 $\{ a_n\},$ $\{ b_n\}$ について, 次が成り立つ.
- (1)
- $2$ 次方程式 \[ x^2-(p+s)x+ps-qr = 0\] の $2$ つの解を $\alpha,$ $\beta$ とおく. このとき, $\{ a_n\}$ の一般項は \[ a_n = \begin{cases} \dfrac{a_2-\beta a_1}{\alpha -\beta}\alpha ^{n-1}-\dfrac{a_2-\alpha a_1}{\alpha -\beta}\beta ^{n-1} & (\alpha \neq \beta ) \\ a_1\alpha ^{n-1}+(a_2-\alpha a_1)(n-1)\alpha ^{n-2} & (\alpha = \beta ) \end{cases}\] である. また, $\{ b_n\}$ の一般項は, この式において $a$ を $b$ に置き換えたものである.
- (2)
- $\lambda$ が $x$ の方程式 \[ x = \dfrac{q+sx}{p+rx} \quad \cdots [*]\] の解であるとき, $\{ a_n+\lambda b_n\}$ は初項 $a_1+\lambda b_1,$ 公比 $p+\lambda r$ の等比数列になる. $[*]$ が相異なる $2$ つの解 $\lambda,$ $\mu$ をもつとき, $\{ a_n\},$ $\{ b_n\}$ の一般項は \[\begin{aligned} a_n &= \frac{\mu (a_1+\lambda b_1)(p+\lambda r)^{n-1}-\lambda (a_1+\mu b_1)(p+\mu r)^{n-1}}{\mu -\lambda}, \\ b_n &= \frac{(a_1+\lambda b_1)(p+\lambda r)^{n-1}-(a_1+\mu b_1)(p+\mu r)^{n-1}}{\lambda -\mu} \end{aligned}\] である.
証明
- (1)
- $[\sharp ]$ から
\[ qb_n = a_{n+1}-pa_n \quad \cdots [1]\]
であり, $n$ を $n+1$ に置き換えると
\[ qb_{n+1} = a_{n+2}-pa_{n+1} \quad \cdots [2]\]
が得られる.
$[1],$ $[2]$ を $q\times [\flat ]$ に代入すると,
\[\begin{aligned}
& a_{n+2}-pa_{n+1} = qra_n+s(a_{n+1}-pa_n) \\
&\therefore a_{n+2}-(p+s)a_{n+1}+(ps-qr)a_n = 0
\end{aligned}\]
となる.
よって, $a_{n+1} = pa_n+q$ 型の漸化式の解法により, $\{ a_n\}$ の一般項が上記のように求まる.
$\{ b_n\}$ の一般項についても同様である. - (2)
- $\lambda$ が $[*]$ の解であるとき, $a_{n+1}+\lambda b_{n+1}$ に $[\sharp ],$ $[\flat ]$ を代入すると, \[\begin{aligned} a_{n+1}+\lambda b_{n+1} &= (p+\lambda r)a_n+(q+\lambda s)b_n \\ &= (p+\lambda r)\left( a_n+\frac{q+\lambda s}{p+\lambda r}b_n\right) \\ &= (p+\lambda r)(a_n+\lambda b_n) \end{aligned}\] となる. $[\ast ]$ が相異なる $2$ つの解 $\lambda,$ $\mu$ をもつとき, \[\left\{\begin{array}{l} a_n+\lambda b_n = (a_1+\lambda b_1)(p+\lambda r)^{n-1} \quad \cdots [1], \\ a_n+\mu b_n = (a_1+\mu b_1)(p+\mu r)^{n-1} \quad \cdots [2] \end{array}\right.\] となるので, $([1]\times\mu -[2]\times\lambda )\div (\mu -\lambda ),$ $([1]-[2])\div (\lambda -\mu )$ から求める等式が得られる.
問題《ペル方程式に関する連立漸化式》
数列 $\{ x_n\},$ $\{ y_n\}$ を
\[\begin{aligned}
x_1 = 3, \quad x_{n+1} &= 3x_n+4y_n \quad \cdots [1], \\
y_1 = 2, \quad y_{n+1} &= 2x_n+3y_n \quad \cdots [2]
\end{aligned}\]
で定める.
- (A)
- 数列 $\{ x_n+ky_n\}$ が公比 $r$ の等比数列になるような定数 $k,$ $r$ の組を $2$ 組求めよ. さらに, 数列 $\{ x_n\},$ $\{ y_n\}$ の一般項を求めよ.
- (B)
- $x_n,$ $x_{n+1},$ $x_{n+2}$ の関係式を求めよ. また, 数列 $\{ x_{n+1}-\alpha x_n\}$ が公比 $\beta$ の等比数列になるような定数 $\alpha,$ $\beta$ の組を $2$ 組求めよ. さらに, 数列 $\{ x_n\},$ $\{ y_n\}$ の一般項を求めよ.
解答例
- (A)
- 数列 $\{ x_n+ky_n\}$ が公比 $r$ の等比数列になるとき, \[\begin{aligned} &x_{n+1}+ky_{n+1} = r(x_n+ky_n) \\ &(3x_n+4y_n)+k(2x_n+3y_n) = r(x_n+ky_n) \quad (\because [1],\ [2]) \\ &(3+2k-r)x_n+(4+3k-rk)y_n = 0 \end{aligned}\] となる. よって, $3+2k-r = 4+3k-rk = 0$ であれば, この等式が成り立つ. $r = 3+2k$ を $4+3k-rk = 0$ に代入して整理すると $2k^2 = 4$ つまり $k = \pm\sqrt 2$ となるから, \[ (k,r) = (\pm\sqrt 2,3\pm 2\sqrt 2)\] は条件を満たす (複号同順). $\{ x_n\pm\sqrt 2y_n\}$ は初項 $3\pm 2\sqrt 2,$ 公比 $3\pm 2\sqrt 2$ の等比数列であるから, \[\begin{aligned} x_n+\sqrt 2y_n &= (3+2\sqrt 2)^n \quad \cdots [3], \\ x_n-\sqrt 2y_n &= (3-2\sqrt 2)^n \quad \cdots [4] \end{aligned}\] が成り立つ. よって, $([3]+[4])\div 2,$ $([3]-[4])\div 2\sqrt 2$ から, \[\begin{aligned} x_n &= \frac{(3+2\sqrt 2)^n+(3-2\sqrt 2)^n}{2}, \\ y_n &= \frac{(3+2\sqrt 2)^n-(3-2\sqrt 2)^n}{2\sqrt 2} \end{aligned}\] が得られる.
- (B)
- $[1]$ から, $x_{n+2} = 3x_{n+1}+4y_{n+1}$ である. ここに $[2]$ を代入して整理すると, \[ x_{n+2} = 3x_{n+1}+8x_n+12y_n\] となる. これと $[1]$ から $y_n$ を消去すると, \[\begin{aligned} &x_{n+2}-3x_{n+1} = 3x_{n+1}-x_n \\ &x_{n+2}-6x_{n+1}+x_n = 0 \end{aligned}\] となる. 数列 $\{ x_{n+1}-\alpha x_n\}$ が公比 $\beta$ の等比数列になるとき, \[\begin{aligned} &x_{n+2}-\alpha x_{n+1} = \beta (x_{n+1}-\alpha x_n) \\ &x_{n+2}-(\alpha +\beta )x_{n+1}+\alpha\beta x_n = 0 \end{aligned}\] となる. よって, $\alpha +\beta = 6,$ $\alpha\beta = 1$ のとき, つまり $(\alpha,\beta ) = (3\mp 2\sqrt 2,3\pm 2\sqrt 2)$ のとき, 上記の等式が成り立つ. $\{ x_{n+1}-(3\mp 2\sqrt 2)x_n\}$ は初項 \[\begin{aligned} x_2-(3\mp 2\sqrt 2)x_1 &= (3\cdot 3+4\cdot 2)-(3\mp 2\sqrt 2)\cdot 3 \\ &= \pm 2\sqrt 2(3\pm 2\sqrt 2), \end{aligned}\] 公比 $3\pm 2\sqrt 2$ の等比数列 (複号同順) であるから, \[\begin{aligned} x_{n+1}-(3-2\sqrt 2)x_n &= 2\sqrt 2(3+2\sqrt 2)^n \quad \cdots [3], \\ x_{n+1}-(3+2\sqrt 2)x_n &= -2\sqrt 2(3-2\sqrt 2)^n \quad \cdots [4] \end{aligned}\] が成り立つ. よって, $([3]-[4])\div 4\sqrt 2$ から, \[ x_n = \frac{(3+2\sqrt 2)^n+(3-2\sqrt 2)^n}{2}\] が得られる. このとき, $[1]$ から \[\begin{aligned} y_n &= \frac{1}{4}x_{n+1}-\frac{3}{4}x_n \\ &= \frac{(3+2\sqrt 2)^{n+1}+(3-2\sqrt 2)^{n+1}}{8} \\ &\qquad -\frac{3(3+2\sqrt 2)^n+3(3-2\sqrt 2)^n}{8} \\ &= \frac{(3+2\sqrt 2)^n\cdot 2\sqrt 2+(3-2\sqrt 2)^n\cdot (-2\sqrt 2)}{8} \\ &= \frac{(3+2\sqrt 2)^n-(3-2\sqrt 2)^n}{2\sqrt 2} \end{aligned}\] である.
参考
- 一般に,「ペル方程式」(Pell's equation) $x^2-dy^2 = 1$ ($d$: 平方数でない正の整数) の整数解について, 次のことが知られている. $x^2-dy^2 = 1$ の正の整数解 $(x,y)$ は必ず存在する. そのような解を用いて $x+y\sqrt d$ の形に表される実数の最小値を $\varepsilon$ とおくと, $x^2-dy^2 = 1$ のすべての正の整数解 $(x,y)$ は, ある正の整数 $n$ に対して $\varepsilon ^n = x+y\sqrt d$ を満たし, \[ (x,y) = \left(\frac{\varepsilon ^n+\varepsilon ^{-n}}{2},\frac{\varepsilon ^n-\varepsilon ^{-n}}{2\sqrt d}\right)\] の形に表される. $d = 2$ のとき $\varepsilon = 3+2\sqrt 2$ であり, 問題の漸化式は $x_{n+1}+y_{n+1}\sqrt 2 = (x_n+y_n\sqrt 2)(3+2\sqrt 2)$ から定まるものである.
- $\lim\limits_{n \to \infty}\dfrac{x_n}{y_n} = \sqrt d$ の成り立つことが知られている ($d = 2$ の場合はこちらを参照).
問題《対称形の連立漸化式》
$a,$ $b,$ $p,$ $q$ を実数とする.
\[\begin{aligned}
a_1 = a, \quad a_{n+1} &= pa_n+qb_n \quad \cdots [1], \\
b_1 = b, \quad b_{n+1} &= qa_n+pb_n \quad \cdots [2]
\end{aligned}\]
で定まる数列 $\{ a_n\},$ $\{ b_n\}$ の一般項を求めよ.
解答例
$[1]+[2],$ $[1]-[2]$ から,
\[\begin{aligned}
a_{n+1}+b_{n+1} &= (p+q)(a_n+b_n), \\
a_{n+1}-b_{n+1} &= (p-q)(a_n-b_n)
\end{aligned}\]
が成り立つ.
これは $\{ a_n+b_n\}$ が初項 $a+b,$ 公比 $p+q$ の等比数列であること, $\{ a_n-b_n\}$ が初項 $a-b,$ 公比 $p-q$ の等比数列であることを意味するから,
\[\begin{aligned}
a_n+b_n &= (a+b)(p+q)^{n-1} \quad \cdots [3], \\
a_n-b_n &= (a-b)(p-q)^{n-1} \quad \cdots [4]
\end{aligned}\]
が得られる.
よって, $([3]+[4])\div 2,$ $([3]-[4])\div 2$ から,
\[\begin{aligned}
a_n &= \frac{(a+b)(p+q)^{n-1}+(a-b)(p-q)^{n-1}}{2}, \\
b_n &= \frac{(a+b)(p+q)^{n-1}-(a-b)(p-q)^{n-1}}{2}
\end{aligned}\]
が得られる.
問題《ピタゴラス変換》
正の整数 $a_1,$ $b_1,$ $c_1$ が $a_1{}^2+b_1{}^2 = c_1{}^2$ を満たすとし, 数列 $\{ a_n\},$ $\{ b_n\},$ $\{ c_n\}$ を
\[ (T) \quad \begin{cases}
a_{n+1} = |2c_n-a_n-2b_n|, \\
b_{n+1} = |2c_n-2a_n-b_n|, \\
c_{n+1} = 3c_n-2a_n-2b_n
\end{cases}\]
で定める.
- (1)
- $a_n{}^2+b_n{}^2 = c_n{}^2$ を示せ.
- (2)
- $c_n > 0$ と $c_n \geqq c_{n+1}$ を示せ.
- (3)
- $c_l > c_{l+1} = c_{l+2}$ なる正の整数 $l$ について, $a_l:b_l:c_l$ を求めよ.
(参考: $1992$ 京都大)
解答例
- (1)
- $a_n{}^2+b_n{}^2 = c_n{}^2 \cdots [1]$ を数学的帰納法で示す.
- (i)
- $n = 1$ のとき. 条件から $[1]$ が成り立つ.
- (ii)
- $n = k$ ($k$: 正の整数) のとき $[1]$ が成り立つとする. このとき, $(T)$ から \[\begin{aligned} &a_{k+1}{}^2+b_{k+1}{}^2-c_{k+1}{}^2 \\ &= (2c_k-a_k-2b_k)^2+(2c_k-2a_k-b_k)^2 \\ &\qquad -(3c_k-2a_k-2b_k)^2 \\ &= (1+4-4)a_k{}^2+(4+1-4)b_k{}^2 \\ &\qquad +(4+4-9)c_k{}^2+(4+4-8)a_kb_k \\ &\qquad +(-8-4+12)b_kc_k+(-4-8+12)c_ka_k \\ &= a_k{}^2+b_k{}^2-c_k{}^2 \\ &= 0 \end{aligned}\] となり, $n = k+1$ のとき $[1]$ が成り立つ.
- (2)
- まず, $c_n > 0$ を数学的帰納法で示す.
- (i)
- $n = 1$ のとき. 条件から $c_n = c_1 > 0$ が成り立つ.
- (ii)
- $n = k$ ($k$: 正の整数) のとき $c_n > 0$ が成り立つとする. このとき, 同値な式変形 \[\begin{aligned} &c_{k+1} > 0 \iff 3c_k > 2(a_k+b_k) \quad (\because (T)) \\ &\iff 9c_k{}^2 > 4(a_k+b_k)^2 \\ &\iff c_k{}^2+8(a_k{}^2+b_k{}^2)-4(a_k+b_k)^2 > 0 \quad (\because [1])\\ &\iff c_k{}^2+4(a_k-b_k)^2 > 0 \quad \cdots [2] \end{aligned}\] において $[2]$ が成り立つから, $n = k+1$ のとき $c_n > 0$ が成り立つ.
また, $c_n \geqq c_{n+1}$ は, 同値な式変形 \[\begin{aligned} c_n \geqq c_{n+1} &\iff c_n \geqq 3c_n-2a_n-2b_n \quad (\because (T)) \\ &\iff a_n+b_n \geqq c_n \\ &\iff (a_n+b_n)^2 \geqq c_n{}^2 \\ &\iff (a_n+b_n)^2 \geqq a_n{}^2+b_n{}^2 \quad (\because [1]) \\ &\iff a_nb_n \geqq 0 \quad \cdots [3] \end{aligned}\] において $[3]$ が成り立つことから従う. - (3)
- (2) の後半で示したことと “ $c_n = c_{n+1} \iff a_nb_n = 0$ ” から,
$c_l > c_{l+1} = c_{l+2}$ のとき $a_lb_l \neq 0,$ $a_{l+1}b_{l+1} = 0$ が成り立つ.
よって, 次のいずれかが起こる.
- (i)
- $a_{l+1} = 0$ のとき. \[\begin{aligned} 2c_l-a_l-2b_l = 0 \quad &\cdots [4], \\ a_l{}^2+b_l{}^2 = c_l{}^2 \quad &\cdots [5] \end{aligned}\] から $a_l$ を消去すると, \[\begin{aligned} 5b_l{}^2-8b_lc_l+3c_l{}^2 &= 0 \\ (b_l-c_l)(5b_l-3c_l) &= 0 \end{aligned}\] となる. $b_l = c_l$ とすると $[5]$ から $a_l = 0$ となって $a_lb_l \neq 0$ に矛盾してしまうから, $b_l = \dfrac{3}{5}c_l$ が成り立つ. このとき, $[4]$ から $a_l = \dfrac{4}{5}c_l$ が成り立つので, $a_l:b_l:c_l = 4:3:5$ である.
- (ii)
- $b_{l+1} = 0$ のとき. (i) と同様に, $a_l:b_l:c_l = 3:4:5$ である.
参考
本問の結果により,「ピタゴラスの $3$ つ組」は $(3k,4k,5k)$ ($k$: 正の整数) の形の「ピタゴラスの $3$ つ組」を共通の祖先にもつことがわかった.
$(T)$ と逆の対応を考えると,「ピタゴラスの $3$ つ組」$(a,b,c)$ からより大きな「ピタゴラスの $3$ つ組」$(a',b',c')$ を生み出す $3$ つの変換
\[\begin{aligned}
&\begin{cases}
a' = a-2b+2c, \\
b' = 2a-b+2c, \\
c' = 2a-2b+3c,
\end{cases} \\
&\begin{cases}
a' = a+2b+2c, \\
b' = 2a+b+2c, \\
c' = 2a+2b+3c,
\end{cases} \\
&\begin{cases}
a' = -a+2b+2c, \\
b' = -2a+b+2c, \\
c' = -2a+2b+3c
\end{cases}
\end{aligned}\]
が得られる.
よって, すべての「原始ピタゴラスの $3$ つ組」は, $(3,4,5)$ から始めて,「ピタゴラス変換」と呼ばれるこれらの変換を毎回 $1$ つ選んで繰り返し行うことによって, つくり出すことができる (バーニング $1963$ 年, ホール $1970$ 年).
