4: 2015-08-23 (日) 02:26:05 osinko  |
5: 2015-08-26 (水) 22:22:52 osinko |
| - | TITLE:数学的帰納と論理式 | + | TITLE:数学的帰納 |
| | #jsmath | | #jsmath |
| | | | |
| | | | |
| | | | |
| - | ***数学的帰納と証明 [#qd4a8c31] | + | ＜漸化式＞ |
| | |等差数列|\({ a }_{ n+1 }-{ a }_{ n }=d\)|\(d=\)公差| | | |等差数列|\({ a }_{ n+1 }-{ a }_{ n }=d\)|\(d=\)公差| |
| | |等比数列|\(\frac { { a }_{ n+1 } }{ { a }_{ n } } =r\)|\(r=\)公比| | | |等比数列|\(\frac { { a }_{ n+1 } }{ { a }_{ n } } =r\)|\(r=\)公比| |
| | //自然数の場合は数列で実数でも単調であれば同じこと？・・・総和であれば漸化式？・・・ | | //自然数の場合は数列で実数でも単調であれば同じこと？・・・総和であれば漸化式？・・・ |
| | //依存すると対応するの違いはあるのか？ | | //依存すると対応するの違いはあるのか？ |
| | + | ***証明の例 [#uf20558d] |
| | + | 以下の漸化式が奇数になる事を証明する |
| | + | \(\begin{cases} { a }_{ n }=3 \\ { a }_{ n+1 }=2{ a }_{ n }-1 \end{cases}\) |
| | + | |
| | + | 規則P: どの\({a}_{n}\)も\(2\)で割ると\(1\)余る（奇数になる） |
| | + | 規則R: \({a}_{n+1}\)は\({a}_{n}\)に対する漸化式 |
| | + | |
| | + | ＜証明＞ |
| | + | basis: |
| | + | +\({a}_{1}=3\)であるから\({a}_{1}\)は\(2\)で割ると\(1\)余る |
| | + | |
| | + | induction step: |
| | + | +\({a}_{n}\)を\(2\)で割ると\(1\)余る数だと仮定する&br;つまり\({a}_{n}=2k+1\)とする（\(\forall k\in \mathbb{N}\)） |
| | + | +そのとき&br;\({a}_{n+1}=2{a}_{n}-1\)&br; \(=2(2k+1)-1=4k+2-1\)&br; \(=4k+1\)&br;であり規則Rが規則Pの性質を保存している。よって\({a}_{n+1}\)も\(2\)で割ると\(1\)余る |
| | + | |
| | + | 以上により、どの\({a}_{n}\)も2で割ると1余り奇数となる |
| | + | |
| | + | ***漸化式の証明のまとめ [#rfddfa61] |
| | + | |
| | + | ＜漸化式の特徴＞ |
| | + | 漸化式は一般項を\(n\)の式で表せない数列も定義できる |
| | + | |
| | + | ＜漸化式の証明のまとめ＞ |
| | + | -basis: 出発点\({a}_{1}\)が性質Pを持っている事を示す |
| | + | -induction step: 既に得られた項\({a}_{n}\)から次の項\({a}_{n+1}\)を作る規則Rが性質Pを保存している事を示す |
| | + | -以上を示せばすべての項が性質Pを持っている事が証明される |
| | + | |
| | + | 重要なのは再帰的なプログラムコードや関数も、これを意識すると非常に性質を制御しやすく作りやすくなるという点 |
![[PukiWiki]](http://unitylabo.s601.xrea.com/xoops/modules/xpwiki/image/pukiwiki.png "[PukiWiki]")
