http://metabolomics.jp/mediawiki/index.php?action=history&feed=atom&title=Aritalab%3ALecture%2FBasic%2FReccurrence 2026-07-04T07:57:16Z Revision history for this page on the wiki MediaWiki 1.19.1 http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Basic/Reccurrence&diff=254479&oldid=prev 2010-10-20T01:10:46Z

<p>New page: ==漸化式== ==一般解== ここでは以下の漸化式の一般解を考えます。 : a&lt;sub&gt;n&lt;/sub&gt; T&lt;sub&gt;n&lt;/sub&gt; = b&lt;sub&gt;n&lt;/sub&gt; T&lt;sub&gt;n-1&lt;/sub&gt; + c&lt;sub&gt;n&lt;/sub&gt; この式を解く...</p> <p><b>New page</b></p><div>==漸化式==<br /> <br /> <br /> ==一般解==<br /> ここでは以下の漸化式の一般解を考えます。<br /> : a&lt;sub&gt;n&lt;/sub&gt; T&lt;sub&gt;n&lt;/sub&gt; = b&lt;sub&gt;n&lt;/sub&gt; T&lt;sub&gt;n-1&lt;/sub&gt; + c&lt;sub&gt;n&lt;/sub&gt;<br /> この式を解くには、邪魔な数列 a&lt;sub&gt;n&lt;/sub&gt;, b&lt;sub&gt;n&lt;/sub&gt; を除くため<br /> : s&lt;sub&gt;n&lt;/sub&gt; = (a&lt;sub&gt;n-1&lt;/sub&gt; a&lt;sub&gt;n-2&lt;/sub&gt; ... a&lt;sub&gt;0&lt;/sub&gt;) / (b&lt;sub&gt;n&lt;/sub&gt; b&lt;sub&gt;n-1&lt;/sub&gt; ... b&lt;sub&gt;1&lt;/sub&gt;)<br /> という数列を導入します。これを和の因子 (summation factor) といいます。ここで s&lt;sub&gt;0&lt;/sub&gt; = 1 とします。<br /> つまり<br /> : s&lt;sub&gt;0&lt;/sub&gt; = 1<br /> : s&lt;sub&gt;1&lt;/sub&gt; = a&lt;sub&gt;0&lt;/sub&gt; / b&lt;sub&gt;1&lt;/sub&gt;<br /> : s&lt;sub&gt;2&lt;/sub&gt; = s&lt;sub&gt;0&lt;/sub&gt; a&lt;sub&gt;1&lt;/sub&gt; / b&lt;sub&gt;2&lt;/sub&gt; = (a&lt;sub&gt;0&lt;/sub&gt; a&lt;sub&gt;1&lt;/sub&gt;) / (b&lt;sub&gt;1&lt;/sub&gt; b&lt;sub&gt;2&lt;/sub&gt;)<br /> : s&lt;sub&gt;3&lt;/sub&gt; = s&lt;sub&gt;2&lt;/sub&gt; a&lt;sub&gt;2&lt;/sub&gt; / b&lt;sub&gt;3&lt;/sub&gt; = (a&lt;sub&gt;0&lt;/sub&gt; a&lt;sub&gt;1&lt;/sub&gt; a&lt;sub&gt;2&lt;/sub&gt;) / (b&lt;sub&gt;1&lt;/sub&gt; b&lt;sub&gt;2&lt;/sub&gt; b&lt;sub&gt;3&lt;/sub&gt;)<br /> です。<br /> 漸化式の両辺に s&lt;sub&gt;n&lt;/sub&gt; をかけてみます。<br /> : s&lt;sub&gt;n&lt;/sub&gt; a&lt;sub&gt;n&lt;/sub&gt; T&lt;sub&gt;n&lt;/sub&gt; = s&lt;sub&gt;n&lt;/sub&gt; b&lt;sub&gt;n&lt;/sub&gt; T&lt;sub&gt;n-1&lt;/sub&gt; + s&lt;sub&gt;n&lt;/sub&gt; c&lt;sub&gt;n&lt;/sub&gt;<br /> ::: = s&lt;sub&gt;n-1&lt;/sub&gt; a&lt;sub&gt;n-1&lt;/sub&gt; T&lt;sub&gt;n-1&lt;/sub&gt; + s&lt;sub&gt;n&lt;/sub&gt; c&lt;sub&gt;n&lt;/sub&gt;<br /> ここで S&lt;sub&gt;n&lt;/sub&gt; = s&lt;sub&gt;n&lt;/sub&gt; a&lt;sub&gt;n&lt;/sub&gt; T&lt;sub&gt;n&lt;/sub&gt; とおきます。<br /> : S&lt;sub&gt;n&lt;/sub&gt; = S&lt;sub&gt;n-1&lt;/sub&gt; + s&lt;sub&gt;n&lt;/sub&gt; c&lt;sub&gt;n&lt;/sub&gt;<br /> :: = s&lt;sub&gt;0&lt;/sub&gt; a&lt;sub&gt;0&lt;/sub&gt; T&lt;sub&gt;0&lt;/sub&gt; + &lt;Big&gt;&amp;Sigma;&lt;/Big&gt;&lt;sup&gt;n&lt;/sup&gt;&lt;sub&gt;k=1&lt;/sub&gt; s&lt;sub&gt;k&lt;/sub&gt; c&lt;sub&gt;k&lt;/sub&gt;<br /> :: = s&lt;sub&gt;1&lt;/sub&gt; b&lt;sub&gt;1&lt;/sub&gt; T&lt;sub&gt;0&lt;/sub&gt; + &lt;Big&gt;&amp;Sigma;&lt;/Big&gt;&lt;sup&gt;n&lt;/sup&gt;&lt;sub&gt;k=1&lt;/sub&gt; s&lt;sub&gt;k&lt;/sub&gt; c&lt;sub&gt;k&lt;/sub&gt;<br /> <br /> これから、はじめの漸化式は<br /> : T&lt;sub&gt;n&lt;/sub&gt; = (1 / s&lt;sub&gt;n&lt;/sub&gt; a&lt;sub&gt;n&lt;/sub&gt;) ( s&lt;sub&gt;1&lt;/sub&gt; b&lt;sub&gt;1&lt;/sub&gt; T&lt;sub&gt;0&lt;/sub&gt; + &lt;Big&gt;&amp;Sigma;&lt;/Big&gt;&lt;sup&gt;n&lt;/sup&gt;&lt;sub&gt;k=1&lt;/sub&gt; s&lt;sub&gt;k&lt;/sub&gt; c&lt;sub&gt;k&lt;/sub&gt;)<br /> と書けることがわかります。<br /> <br /> 確認のため、 n = 1 を代入してみると<br /> : T&lt;sub&gt;1&lt;/sub&gt; = (1 / s&lt;sub&gt;1&lt;/sub&gt; a&lt;sub&gt;1&lt;/sub&gt;) ( s&lt;sub&gt;1&lt;/sub&gt; b&lt;sub&gt;1&lt;/sub&gt; T&lt;sub&gt;0&lt;/sub&gt; + s&lt;sub&gt;1&lt;/sub&gt; c&lt;sub&gt;1&lt;/sub&gt;) = (1 / a&lt;sub&gt;1&lt;/sub&gt;)(b&lt;sub&gt;1&lt;/sub&gt; T&lt;sub&gt;0&lt;/sub&gt; + c&lt;sub&gt;1&lt;/sub&gt;)<br /> となり正しい結果になりました。</div>

Adm