【数列】どんな漸化式も解きうる方法、近似的な補間!

更新日時:2020/11/01

数学数列近似的な補間

GOODされた数:48 回

プロローグ

どうも、安田です。
本記事では、どんな二項間漸化式を持つ数列でも一般項を求められるという優れものを紹介します。もちろん欠点も在りますが、対応している数列は全てであり、必ず手計算可能な形となっています。

これを発見した経緯は以下の記事のような感じです。 近似的な補間を用いて数列$Y$を近似する記事

近似的な補間

近似的な補間の定義と証明

近似的な補間というのは、今回紹介する、数列の解法の呼び名です。その名の通り、近似をしながら補間も行うというものになっています。
具体的な内容は以下の通りです。

近似的な補間 \begin{equation} a_{n+1} = f(a_n) \end{equation} という漸化式を持つ数列について、 \begin{equation} \begin{cases} g_1(1) = a_1 \\ g_{m+1}(n) = g_m(n) + g_m(n+1) - f(g_m(n)) + \displaystyle \sum_{k=1}^{n}(f(g_m(k)) - g_m(k+1)) \end{cases} \end{equation} を満たすいかなる関数列$\{g_m(n)\}$においても、少なくとも \begin{equation} \begin{cases} a_n = g_m(n) \ \ \ \ (n \leqq m)\\ a_n = \lim_{m \to \infty} g_m(n) \end{cases} \end{equation} を満たす。

この有用性や価値については後のセクションで書きますので、まずは証明をします。

\[ g_m(n) = a_n \] 少なくとも成り立つ範囲を $n \leqq N_m$ とする。

$(\alpha) n \leqq N_m$ のとき
この時 $g_m(k) = a_k \ (k \leqq n)$ が成り立つ事から、 \[ g_m(k+1) = f(g_m(k)) \ \ \ \ (k \leqq n - 1) \] が成り立つ。よって \begin{eqnarray*} \sum_{k=1}^{n-1} \left\{ f(g_m(k)) - g_m(k+1) \right\} &=& 0 \\ \sum_{k=1}^{n} \left\{ f(g_m(k)) - g_m(k+1) \right\} &=& f(g_m(n)) - g_m(n+1) \end{eqnarray*} である。ゆえに
\begin{eqnarray*} g_{m+1}(n) &=& g_m(n) + g_m(n+1) - f(g_m(n)) + f(g_m(n)) - g_m(n+1) \\ g_{m+1}(n) &=& g_m(n) \\ g_{m+1}(n) &=& a_n \end{eqnarray*} が成立する。

$(\beta) n = N_m + 1$ のとき
$g_m(k) = a_k (k \leqq N_m)$ が成り立つ事から、 \[ g_m(k+1) = f(g_m(k)) \ \ \ \ (k \leqq N_m - 1) \] が成り立つ。よって \begin{eqnarray*} \sum_{k=1}^{N_m - 1} \left\{ f(g_m(k)) - g_m(k+1) \right\} &=& 0 \\ \sum_{k=1}^{n} \left\{ f(g_m(k)) - g_m(k+1) \right\} &=& f(g_m(n-1)) - g_m(n) + f(g_m(n)) - g_m(n+1) \end{eqnarray*} である。ゆえに \begin{eqnarray*} g_{m+1}(n) &=& g_m(n) + g_m(n+1) - f(g_m(n)) + f(g_m(n-1)) - g_m(n) + f(g_m(n)) - g_m(n+1) \\ g_{m+1}(n) &=& f(g_m(n-1)) \\ g_{m+1}(n) &=& f(a_{n-1}) \\ g_{m+1}(n) &=& a_n \end{eqnarray*} が成立する。

$(\alpha), (\beta)$より \[ N_{m+1} = N_m + 1 \] が成り立つ。$g_1(1)=a_1$ より $N_1 = 1$ なので \[ N_m = m \] よって、少なくとも \begin{equation} g_m(n) = a_n \ \ \ \ (n \leqq m) \end{equation} が成り立つ。

こう証明してみると当たり前の事のようです。ちなみに、上の証明は帰納法のように見えますが、私は$N_m$の漸化式を発見するプロセスだという考えのもとで書きましたので、帰納法だという記述は省きました。

また「近似」の要素についてですが、この補間では増加量の誤差を修正するという手法を取っている事に着目すると分かります。$n < m$ のような値が一致しない部分では近似が働きます。この補間では、漸化式との増加量の誤差
\[ g_m(n+1) - f(g_m(n)) \] の$1$から$n$までの総和を引くという操作によって近似を成し遂げています。
しかしながら、特異な変化を示す関数の場合などは近似されない場合があるため、「近似されていく」事の証明は不可能です

有限回の計算による一般項導出

近似的な補間の定義を見る限り、完全な一般項の導出には無限回の計算を要するように見えますが、$a_n$の$g_1(n)$の組み合わせによっては有限回の計算により一般項を求める事も可能です。近似的な補間の次の課題は、このような$g_1(n)$の条件を発見する事にあるのかもしれませんね
とりあえず簡単な実例を示します。

\begin{equation} \begin{cases} a_{n+1} = a_n + 1 \\ a_1 = 1 \end{cases} \end{equation} つまりは \[ a_n = n \]

について考えます。この時、ちょっとあり得なさそうな関数を$g_1(n)$に合わせてみます。(この時、$g_1(1)$の値が一致するようにすることを忘れないようにする。。)

\[ g_1(n) = 2^{n-1} \]

この時$g_2(n)$がどうなるか計算して確かめてみます。

\begin{eqnarray*} g_2(n) &=& g_1(n) + g_1(n+1) - f(g_1(n)) + \sum_{k=1}^{n}(f(g_1(k)) - g_1(k+1)) \\ &=& 2^{n-1} + 2^n - 2^{n-1} - 1 + \sum_{k=1}^n \left( 2^{k-1} + 1 - 2^k \right) \\ &=& 2^n - 1 + \sum_{k=1}^{n} \left( 1 - 2^{k-1} \right) \\ &=& 2^n - 1 + n - \frac{2^n - 1}{2 - 1} \\ &=& n \end{eqnarray*}

既に一般項と一致している事が分かります。このように、実際に有限回で足りる場合があるという事が分かったと思います。

ここで、結局はピンポイントでそういった関数を見つけないといけないため、数列を解く事と同じ程の難易度なのではないのか、と感じるかもしれませんが、実は難易度は下がっています。
上の例で $g_1(n) = 2n - 1$ を考えると成り立つ事が分かります。これは選択肢が広がった事を意味します。これは \[ g_{m+1}(n) = a_n \] の解 $\{g_m(n)\}$ が複数個存在している事によります。

以上の事から、近似的な補間は「漸化式を解く」事の難易度を下げる効果がある事が分かります。

逆を用いた問題の解決

\begin{equation} \begin{cases} g_1(n) = n\cos(n - 1) \\ g_{m+1}(n) = g_m(n) + g_m(n+1) - f(g_m(n)) + \displaystyle \sum_{k=1}^{n} (2g_m(n) - g_{m+1}(n)) \end{cases} \end{equation} という関数列$\{g_m(n)\}$の極限 \[ \lim_{m\to \infty} g_m(n) \] を求めなさい。ただし$n$は整数である。

この問題は近似的な補間を見た後だと異常に簡単に見えますが、近似的な補間を知らなければ全く分からないと思います。何故なら、最初に答えを予想しないと答えを出す事が出来ないからです。
もちろん近似的な補間の証明を用いれば

\[ \lim_{m \to \infty} g_m(n) = 2^{n-1} \]

という事が分かります。

このように、近似的な補間により、一定の形をした漸化式を持つ関数列の極限を求める事が出来ます。ほとんど使い道がありませんが、いつかこういう形が出来た時に役立つといいなと思います。

以上が近似的な補間の紹介でした。現在ではこれだけの性質しか発見出来ていませんが、これからも研究するので随時記事を書きます。
それでは、お疲れさまでした。

この記事いいね!


コメント送信フォームまで飛ぶ

この記事には0件のコメントがあります。


変換


※上の変換器は、TeXが正しいかどうかの確認に使ってください。
※TeXを入力する場合は、コメント本文に、$\$$ または、$\verb|\|$[, $\verb|\|$]で囲った中にTeX表示をそのまま挿入してください。
※URLは、自動的にハイパーリンクに変形されます。
※他のコメントに返信する場合は、「#コメント番号」を挿入してください。
※日本語を含まないコメントはスパムと認定されます。
※Comment including no japanese will be regarded as spam.