タグ: 漸化式

動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える動的計画法を「部分問題の依存関係が DAG なら位相順に一度ずつ解けばよい」という原理として定式化し、フィボナッチ数列の指数時間再帰が O(n) になる仕組みと、0-1 ナップサック問題の漸化式・O(nW) 表計算・解の復元を証明付きで示す。情報科学アルゴリズムとデータ構造学部動的計画法メモ化ナップサック問題最適部分構造漸化式約 45 分
漸化式と母関数：特性方程式・行列の冪・Fibonacci 数・分割数1 次・2 次の線形漸化式を特性方程式で解き、行列の冪を剰余で計算し、分数型漸化式を固定点で直す。Fibonacci 数の整除性、母関数への数の代入、Euler の分割恒等式を証明つきで導く。数学高校数学：数と式・整数・数列高校〜一般漸化式特性方程式母関数フィボナッチ数分割数約 28 分
数列と関数の極限：「限りなく近づく」を ε-N で言い直し、e まで進む高校の「限りなく近づく」を ε-N の定義で言い直し、等比数列・無限等比級数・調和級数の発散・ネイピア数 e・Stolz–Cesàro の定理・漸化式の収束を、定義から順に証明する。数学高校数学：関数と微分積分高校〜一般極限数列ネイピア数連続性漸化式約 24 分