漸化式ぜんかしきrecurrence relationの型かたと方針ほうしん-基本演習きほんえんしゅう

date2026-07-14document_iddoc_eb930e3ca79c255dbc71afe0a40c02f0description漸化式の型判定、固定点、階差、特性方程式、連立化、帰納法を確認する基本演習である。prerequisites漸化式の型と方針 / シフト作用素と漸化式 / 等差数列と等比数列type問題演習content_typeexercisestatusactive

mathsequencerecurrenceexercise

data/lecture/math/sequence/recurrence-types-and-strategies.lecture.n.md data/lecture/math/sequence/shift-operators-and-recurrences.lecture.n.md

1演習えんしゅう方針ほうしん

各かく問題もんだいで、最初さいしょに「差さを見みるのか、比ひを見みるのか、固定点こていてんを引ひくのか、階差かいさを置おくのか、連立れんりつ化かするのか、帰納法きのうほうに切きり替かえるのか」を明示めいじする。

2問題もんだい 1：固定点こていてんを引ひく

a_{n + 1} = 3 a_{n} + 7, a_{1} = 1

の一般いっぱん項こうを求もとめよ。

2.1解答例かいとうれい

定数ていすうつき一次いちじ型かたなので、固定点こていてんを探さがす。

α = 3 α + 7

より $α = - 7 / 2$ である。したがって

a_{n + 1} - α = 3 (a_{n} - α)

である。よって

a_{n} - α = 3^{n - 1} (a_{1} - α)

となる。 $a_{1} = 1$ 、 $α = - 7 / 2$ より

a_{n} = - \frac{7}{2} + \frac{9}{2} \cdot 3^{n - 1}

である。

3問題もんだい 2：階差かいさを足たす

a_{n + 1} - a_{n} = 2 n + 1, a_{1} = 0

の一般いっぱん項こうを求もとめよ。

3.1解答例かいとうれい

差分さぶん型かたなので、両辺りょうへんを足たす。

a_{n} = a_{1} + \sum_{k = 1}^{n - 1} (2 k + 1)

である。したがって

a_{n} = \sum_{k = 1}^{n - 1} (2 k + 1) = 2 \frac{(n - 1) n}{2} + (n - 1) = n^{2} - 1

である。

4問題もんだい 3：等比とうひ的てきな差さを取とる

a_{n + 1} = 2 a_{n} + n, a_{1} = 0

の一般いっぱん項こうを求もとめよ。

4.1解答例かいとうれい

一次いちじ非ひ同次どうじ型かたである。 $p = 2$ なので

b_{n} = \frac{a_{n}}{2^{n - 1}}

と置おく。すると

b_{n + 1} - b_{n} = \frac{n}{2^{n}}

である。よって

b_{n} = \sum_{k = 1}^{n - 1} \frac{k}{2^{k}}

であり、

a_{n} = 2^{n - 1} \sum_{k = 1}^{n - 1} \frac{k}{2^{k}}

である。さらに

\sum_{k = 1}^{m} \frac{k}{2^{k}} = 2 - \frac{m + 2}{2^{m}}

を用もちいて $m = n - 1$ とすると、

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

である。

5問題もんだい 4：階差かいさを新あたらしい数列すうれつにする

a_{n + 2} - a_{n + 1} = 3 (a_{n + 1} - a_{n}), a_{1} = 1, a_{2} = 4

の一般いっぱん項こうを求もとめよ。

5.1解答例かいとうれい

$b_{n} = a_{n + 1} - a_{n}$ と置おくと、 $b_{n + 1} = 3 b_{n}$ である。 $b_{1} = a_{2} - a_{1} = 3$ なので

b_{n} = 3^{n}

である。したがって

a_{n} = a_{1} + \sum_{k = 1}^{n - 1} b_{k} = 1 + \sum_{k = 1}^{n - 1} 3^{k} = 1 + \frac{3 (3^{n - 1} - 1)}{2}

である。

6問題もんだい 5：隣接りんせつ 3 項こう間かんと特性とくせい方程式ほうていしき

a_{n + 2} = 5 a_{n + 1} - 6 a_{n}, a_{0} = 1, a_{1} = 2

の一般いっぱん項こうを求もとめよ。

6.1解答例かいとうれい

定数ていすう係数けいすうの隣接りんせつ 3 項こう間まなので、 $P (E) a = 0$ と見みる。特性とくせい方程式ほうていしきは

r^{2} - 5 r + 6 = 0

である。よって

(r - 2) (r - 3) = 0

であり、解かいは

a_{n} = C 2^{n} + D 3^{n}

の形かたちである。初期条件しょきじょうけんから

C + D = 1, 2 C + 3 D = 2

である。これを解とくと $D = 0$ 、 $C = 1$ である。したがって

a_{n} = 2^{n}

である。

7問題もんだい 6：和わ $S_{n}$ を消けす

$S_{n} = a_{1} + \dots + a_{n}$ とし、

a_{n + 1} = 2 S_{n} + 1, a_{1} = 1

とする。 $a_{n}$ を求もとめよ。

7.1解答例かいとうれい

$S_{n}$ が出でるので、1 つ進すすめて差さを取とる。

a_{n + 2} = 2 S_{n + 1} + 1

である。したがって

a_{n + 2} - a_{n + 1} = 2 (S_{n + 1} - S_{n}) = 2 a_{n + 1}

より

a_{n + 2} = 3 a_{n + 1}

である。 $a_{2} = 2 S_{1} + 1 = 3$ なので、 $n [PARSE ERROR: Undefined("Command(\"ge\")")] 2$ で

a_{n} = 3^{n - 1}

である。 $a_{1} = 1$ もこの式しきに一致いっちする。

8問題もんだい 7：連立れんりつ化かする

\begin{cases} a_{n+1}=2a_n+b_n\\ b_{n+1}=a_n+2b_n \end{cases}\begin{cases} a_{n+1}=2a_n+b_n\\ b_{n+1}=a_n+2b_n \end{cases}

とする。 $u_{n} = a_{n} + b_{n}$ 、 $v_{n} = a_{n} - b_{n}$ の漸化式ぜんかしきを求もとめよ。

8.1解答例かいとうれい

和わを取とると

u_{n + 1} = a_{n + 1} + b_{n + 1} = 3 a_{n} + 3 b_{n} = 3 u_{n}

である。差さを取とると

v_{n + 1} = a_{n + 1} - b_{n + 1} = a_{n} - b_{n} = v_{n}

である。したがって、連立れんりつ漸化式ぜんかしきは $u_{n}$ と $v_{n}$ に分離ぶんりされる。

9問題もんだい 8：帰納法きのうほうで性質せいしつを示しめす

a_{n + 1} = \frac{a_{n} + 2}{a_{n} + 1}, a_{1} > 0

で定さだまる数列すうれつについて、すべての $n$ で $a_{n} > 0$ を示しめせ。

9.1解答例かいとうれい

性質せいしつ証明しょうめいなので数学的帰納法すうがくてききのうほうを使つかう。 $n = 1$ では仮定かていより $a_{1} > 0$ である。

$a_{n} > 0$ と仮定かていする。このとき $a_{n} + 2 > 0$ かつ $a_{n} + 1 > 0$ である。したがって

a_{n + 1} = \frac{a_{n} + 2}{a_{n} + 1} > 0

である。よって帰納法きのうほうにより、すべての $n$ で $a_{n} > 0$ である。

10問題もんだい 9：合同ごうどう式しきで余あまりを追おう

a_{n + 1} = 3 a_{n} + 2, a_{1} = 0

で定さだまる数列すうれつについて、 $a_{n}$ を 5 で割さった余あまりの遷移せんいを求もとめよ。

10.1解答例かいとうれい

余あまりだけを問とうので、合同ごうどう式しきを見みる。

a_{n + 1} \equiv 3 a_{n} + 2 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5

である。 $r_{n}$ を $a_{n}$ の 5 で割さった余あまりとすると、

r_{n + 1} \equiv 3 r_{n} + 2 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5

である。 $r_{1} = 0$ から順じゅんに計算けいさんすると

r_{2} \equiv 2, r_{3} \equiv 3, r_{4} \equiv 1, r_{5} \equiv 0

である。したがって余あまりは

0, 2, 3, 1, 0, 2, 3, 1, \dots

と周期しゅうき 4 で繰くり返かえす。

11問題もんだい 10：最大公約数さいだいこうやくすうを 1 段だん戻もどす

a_{n + 1} = a_{n} + a_{n - 1}

で定さだまる整数列せいすうれつについて、

[PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n + 1}, a_{n}) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n}, a_{n - 1})

を示しめせ。

11.1解答例かいとうれい

互除ごじょ法ほう型かたなので、最大公約数さいだいこうやくすうを余あまりへ落おとす。

a_{n + 1} = a_{n} + a_{n - 1}

より

[PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n + 1}, a_{n}) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n} + a_{n - 1}, a_{n})

である。任意にんいの整数せいすう $x, y$ について

[PARSE ERROR: Undefined("Command(\"gcd\")")] (x + y, x) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (y, x)

が成立せいりつするので、 $x = a_{n}$ 、 $y = a_{n - 1}$ とすれば

[PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n} + a_{n - 1}, a_{n}) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n - 1}, a_{n}) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n}, a_{n - 1})

である。

漸化式ぜんかしきrecurrence relationの型かたと方針ほうしん-基本演習きほんえんしゅう

1演習えんしゅう方針ほうしん

2問題もんだい 1：固定点こていてんを引ひく

2.1解答例かいとうれい

3問題もんだい 2：階差かいさを足たす

3.1解答例かいとうれい

4問題もんだい 3：等比とうひ的てきな差さを取とる

4.1解答例かいとうれい

5問題もんだい 4：階差かいさを新あたらしい数列すうれつにする

5.1解答例かいとうれい

6問題もんだい 5：隣接りんせつ 3 項こう間かんと特性とくせい方程式ほうていしき

6.1解答例かいとうれい

7問題もんだい 6：和わ SnS_n を消けす

7.1解答例かいとうれい

8問題もんだい 7：連立れんりつ化かする

8.1解答例かいとうれい

9問題もんだい 8：帰納法きのうほうで性質せいしつを示しめす

9.1解答例かいとうれい

10問題もんだい 9：合同ごうどう式しきで余あまりを追おう

10.1解答例かいとうれい

11問題もんだい 10：最大公約数さいだいこうやくすうを 1 段だん戻もどす

11.1解答例かいとうれい

12関連講義かんれんこうぎ

7問題もんだい 6：和わ $S_{n}$ を消けす