• ハノイの塔 • • • フィボナッチ数列 • • 漸化式等比数列と等比級数再帰的プログラミング自然対数の底 • 無理数に収束する有理数列数列 1  ルール • 柱3本 • 皿𝑛枚 • 移動1枚/回 • いつも大小関係 C A B  移築完成に必要な最小の移動回数 • ヒント  必ず通過する状態は？  𝑛 − 1枚の回数 𝑀(𝑛 − 1)との関係は？  数列𝑀(𝑛)の漸化式は？数列 𝑀(𝑛)？ 2 • A→BにはCを通過する • A→Cの回数 = 𝑀(𝑛 − 1) • C→Bの回数 = 1+𝑀 𝑛−1 𝑀 𝑛 = 𝑀(𝑛 − 1) + 1 + 𝑀(𝑛 − 1) 𝐴→𝐶 𝐶→𝐵 = 2𝑀 𝑛−1 +1 • 一般項は？数列 3 𝑀 𝑛 =2𝑀 𝑛−1 +1 𝑀 1 =1 𝑦 𝑦 = 2𝑥 + 1 𝑥=𝑦 𝑌 𝑦1 特徴的な点は，２直線の交点 𝑋 = 𝑥 + 1, 𝑌 = 𝑦 + 1 𝑥1 𝑥2 𝑀′ 𝑛 ≡ 𝑀 𝑛 + 1 𝑀’ 𝑛 = 2 𝑀’ 𝑛 − 1 𝑀’ 1 =2 𝑥 𝑋 𝑌 = 2𝑋 𝑋=𝑌 公比２の等比数列の漸化式で 𝑀′ 𝑛 = 2𝑛 , ∴ 𝑀 𝑛 = 2𝑛 − 1 数列 4  等比数列の第n部分和を簡潔に表せ 𝑆𝑛 = 𝑎0 𝑟 𝑘 =? 𝑎𝑘 = 𝑘=0,𝑛−1 𝑘=0,𝑛−1  等比級数の極限値を公比により分類せよ ? ? ? lim 𝑆𝑛 = 𝑛→∞ 数列 5  等比級数 𝑎𝑛 = 𝑎0 𝑟 𝑛 , 𝑛 = 0,1,2, ⋯ 𝑛 1 − 𝑟 𝑆𝑛 = 𝑎0 (1 + 𝑟 + 𝑟 2 + ⋯ + 𝑟 𝑛−1 ) = 𝑎0 × 1−𝑟  極限値，収束 𝑆 = lim 𝑆𝑛 𝑛→∞ 𝑎0 ⋯ 𝑟 <1 𝑛 1−𝑟 1−𝑟 = 𝑎0 × lim = 発散振動 ⋯ 𝑟 = −1 𝑛→∞ 1 − 𝑟 発散無限大 ⋯ 𝑟 = 1, 𝑟 > 1 数列 6  有理数とは何か，どんな性質をもつか？  無理数とは何か，実数とは何か？  一般項が有理数の数列で，極限値が無理数になる例を挙げよ．その漸化式を示せ．数列 7  実数：有理数と無理数 • 有理数：整数の比 • 無理数：有理数でない数 • 実数は四則演算と極限操作について閉じている  数直線のどこを切っても実数にあたる  有理数列の極限と無理数 𝑎𝑛 + 2 1 𝑎𝑛+1 = =1+ , 𝑎1 = 1 → lim𝑎𝑛 = 2 𝑎𝑛 + 1 𝑎𝑛 + 1 𝑛 1 𝑒𝑛 = 1 + , lim𝑒𝑛 = 𝑒 𝑛 数列 8  次の用語を調べて，簡潔に説明せよ • プログラミング • 再帰的プログラミング  𝑛を入力すると 𝐹 𝑛 = 𝑛! = 𝑛 × 𝑛 − 1 × ⋯ × 2 × 1 の値を計算する再帰的なプログラムを設計せよ数列 9  再帰的プログラミング • 入力が自然数𝑛のとき，出力𝐹(𝑛)を求めるプログラム • 𝐹(𝑛) を 𝑛 の関数として（直接の計算法を）示さず • 𝑭 𝒏 を 𝑭 𝒏 − 𝟏 の関数として書く．すなわち漸化式を与える．初項を与える． • 変化（漸化式）に注目すると理解しやすい．わかりやすい • 計算量が著しく増えることがある 例 • 𝐹 𝑛 = 𝐹 𝑛 − 1 × 𝑛, 𝐹 1 = 1 数列 10  「数学的帰納法」はどんな証明法か，調べて簡潔に記せ．数列 11  自然数の性質 • どの自然数にも，つぎの自然数がある  自然数𝑛を変数とする命題 𝑃(𝑛) • 𝑃(𝑛)の例: 𝑛 ≥ 2に対して 1 + ℎ 𝑛 > 1 + 𝑛ℎ が成り立つ  数学的帰納法（雰囲気は漸化式） • 𝑛の具体的な値によらずに， 𝑃 𝑛 を仮定すると 𝑃(𝑛 + 1)が成り立つことを示す． 𝑃 1 が正しいことを示す（上例では𝑃(2)）．数列 12  フィボナッチ数列 𝑎𝑛+2 = 𝑎𝑛+1 + 𝑎𝑛 , 𝑎2 = 𝑎1 = 1 3 = 𝑎3 を求める」再帰的プログラミングの手順を示す．  図は「3を入力して𝐹  図を観察して • F(5)を求める手順の図を描け． • F(3)とF(5)で計算の手間（計算量）の差について考察せよ．数列 13  𝑎𝑛 : 𝑎𝑛+2 = 𝑎𝑛+1 + 𝑎𝑛 , 𝑎2 = 1, 𝑎1 = 1 • ウサギの繁殖の予測から! 1 • 𝑎𝑛 = 𝛼 𝑛 − 𝛽𝑛 , 𝛼, 𝛽 = 5  黄金比 1+ 5 2 1± 5 2 ≃ 1.6, 𝑥 2 − 𝑥 − 1 = 0  漸化式が分かりやすい • 再帰的プログラミング  見やすい  計算量が指数的に増加する数列 14  「二項定理」を調べて，簡潔に説明せよ． 𝑥 𝑁 𝑁 1+𝑥  数列 1 + • 単調増加 =?, 1 1+ 𝑁 𝑁 𝑁 =? 1 𝑁 の次の性質を示す方法を考察せよ． 𝑁 1 1+ 𝑁 • 有界 1+ 𝑁 1 < 1+ 𝑁+1 𝑁+1 1 1 1 1 <1+1+ + + +⋯<1+ <3 1 2 2×2 2×2×2 1−2 数列 15  複利計算： • 年利𝑥→日歩→N分割 • 𝐴𝑛 = 𝐴0 1 + 𝑥 𝑛 → 𝐴 𝑁 = 𝐴0 1 𝑥 𝑁 + 𝑁  二項定理 • 𝑥 𝑁 1+ =1+𝑥 𝑁 1 ⋯ + 𝑁 𝑥𝑁 𝑁 𝑁→∞ + 1 1 2! ⋅ 1− 1 𝑁 𝑥2 + 1 1 3! ⋅ 1− 1 𝑁 1 2 1 3 1 + 𝑥 + 2! 𝑥 + 3! 𝑥 +⋯ ⋅ 1− 2 𝑁 𝑥 3 +⋅  無限分割の極限 • 𝑒 = lim 1 𝑁→∞ 1 𝑁 + 𝑁 = 2.7 … 無理数数列 16