離散数学-漸化式
この章では、再帰的手法を使用してシーケンスを導出し、カウントの問題を解決する方法について説明します。シーケンスの項を再帰的に見つける手順は、recurrence relation。線形漸化式の理論とその解を研究します。最後に、漸化式を解くための母関数を紹介します。
定義
漸化式は、次の項が前の項の関数であるシーケンスを再帰的に定義する方程式です（$ F_n $を$ F_i $と$ i <n $の組み合わせとして表現します）。
Example −フィボナッチ数列− $ F_n = F_ {n-1} + F_ {n-2} $、ハノイの塔− $ F_n = 2F_ {n-1} + 1 $
線形漸化式
次数kまたは次数kの線形漸化式は、$ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_kx_の形式の漸化式です。 {nk} $（$ A_n $は定数で、$ A_k \ neq 0 $）は、1次多項式としての一連の数値です。
これらは線形漸化式のいくつかの例です-
| 漸化式 | 初期値 | ソリューション |
|---|---|---|
| F n = F n-1 + F n-2 | a 1 = a 2 = 1 | フィボナッチ数 |
| F n = F n-1 + F n-2 | a 1 = 1、a 2 = 3 | リュカ数 |
| F n = F n-2 + F n-3 | a 1 = a 2 = a 3 = 1 | パドヴァン数列 |
| F n = 2F n-1 + F n-2 | a 1 = 0、a 2 = 1 | ペル数 |
線形漸化式を解く方法
2次の線形漸化式が− $ F_n = AF_ {n-1} + BF_ {n-2} $であると仮定します。ここで、AとBは実数です。
上記の漸化式の特性式は次のとおりです。
$$ x ^ 2-Ax-B = 0 $$
根を見つける間に3つのケースが発生する可能性があります-
Case 1−この方程式が$（x- x_1）（x- x_1）= 0 $として因数分解され、2つの異なる実根$ x_1 $と$ x_2 $が生成される場合、$ F_n = ax_1 ^ n + bx_2 ^ n $が解です。[ここで、aとbは定数です]
Case 2 −この方程式が$（x- x_1）^ 2 = 0 $として因数分解され、単一の実根$ x_1 $が生成される場合、$ F_n = a x_1 ^ n + bn x_1 ^ n $が解です。
Case 3 −方程式が2つの異なる複素根、$ x_1 $と$ x_2 $を極形式で生成する場合$ x_1 = r \ angle \ theta $と$ x_2 = r \ angle（-\ theta）$、$ F_n = r ^ n （a cos（n \ theta）+ b sin（n \ theta））$が解です。
Problem 1
漸化式$ F_n = 5F_ {n-1} -6F_ {n-2} $を解きます。ここで、$ F_0 = 1 $および$ F_1 = 4 $
Solution
漸化式の特性方程式は次のとおりです。
$$ x ^ 2--5x + 6 = 0、$$
したがって、$（x-3）（x-2）= 0 $
したがって、根は-
$ x_1 = 3 $および$ x_2 = 2 $
ルーツは本物ではっきりしています。つまり、これはケース1の形式です。
したがって、解は次のようになります。
$$ F_n = ax_1 ^ n + bx_2 ^ n $$
ここで、$ F_n = a3 ^ n + b2 ^ n \（As \ x_1 = 3 \および\ x_2 = 2）$
したがって、
$ 1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b $
$ 4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b $
これらの2つの方程式を解くと、$ a = 2 $と$ b = -1 $が得られます。
したがって、最終的な解決策は次のとおりです。
$$ F_n = 2.3 ^ n +（-1）。2 ^ n = 2.3 ^ n-2 ^ n $$
Problem 2
漸化式を解きます-$ F_n = 10F_ {n-1} -25F_ {n-2} $ここで、$ F_0 = 3 $および$ F_1 = 17 $
Solution
漸化式の特性方程式は次のとおりです。
$$ x ^ 2-10x -25 = 0 $$
したがって、$（x-5）^ 2 = 0 $
したがって、単一の実根$ x_1 = 5 $があります。
単一の実数値ルートがあるため、これはケース2の形式になります。
したがって、解は次のようになります。
$ F_n = ax_1 ^ n + bnx_1 ^ n $
$ 3 = F_0 = a.5 ^ 0 +（b）（0.5）^ 0 = a $
$ 17 = F_1 = a.5 ^ 1 + b.1.5 ^ 1 = 5a + 5b $
これらの2つの方程式を解くと、$ a = 3 $と$ b = 2/5 $が得られます。
したがって、最終的な解は次のようになります。− $ F_n = 3.5 ^ n +（2/5）.n.2 ^ n $
Problem 3
漸化式$ F_n = 2F_ {n-1} -2F_ {n-2} $を解きます。ここで、$ F_0 = 1 $および$ F_1 = 3 $
Solution
漸化式の特性方程式は次のとおりです。
$$ x ^ 2 -2x -2 = 0 $$
したがって、根は-
$ x_1 = 1 + i $および$ x_2 = 1-i $
極形式では、
$ x_1 = r \ angle \ theta $および$ x_2 = r \ angle（-\ theta）、$ここで、$ r = \ sqrt 2 $および$ \ theta = \ frac {\ pi} {4} $
ルーツは架空のものです。したがって、これはケース3の形式です。
したがって、解は次のようになります。
$ F_n =（\ sqrt 2）^ n（a cos（n。\ sqcap / 4）+ b sin（n。\ sqcap / 4））$
$ 1 = F_0 =（\ sqrt 2）^ 0（a cos（0。\ sqcap / 4）+ b sin（0。\ sqcap / 4））= a $
$ 3 = F_1 =（\ sqrt 2）^ 1（a cos（1。\ sqcap / 4）+ b sin（1。\ sqcap / 4））= \ sqrt 2（a / \ sqrt 2 + b / \ sqrt 2 ）$
これらの2つの方程式を解くと、$ a = 1 $と$ b = 2 $が得られます。
したがって、最終的な解決策は次のとおりです。
$ F_n =（\ sqrt 2）^ n（cos（n。\ pi / 4）+ 2 sin（n。\ pi / 4））$
不均一な漸化式と特定の解決策
漸化式は、次の形式の場合、不均一と呼ばれます。
$ F_n = AF_ {n-1} + BF_ {n-2} + f（n）$ここで、$ f（n）\ ne 0 $
関連する同次漸化式は$ F_n = AF_ {n–1} + BF_ {n-2} $です。
不均一な漸化式の解$（a_n）$には、2つの部分があります。
最初の部分は、関連する同次漸化式の解$（a_h）$であり、2番目の部分は特定の解$（a_t）$です。
$$ a_n = a_h + a_t $$
最初の部分の解決策は、前のセクションで説明した手順を使用して行われます。
特定の解決策を見つけるために、適切な試行解決策を見つけます。
$ f（n）= cx ^ n $とします; $ x ^ 2 = Ax + B $を関連する同次漸化式の特性方程式とし、$ x_1 $と$ x_2 $をその根とします。
$ x \ ne x_1 $および$ x \ ne x_2 $の場合、$ a_t = Ax ^ n $
$ x = x_1 $、$ x \ ne x_2 $の場合、$ a_t = Anx ^ n $
$ x = x_1 = x_2 $の場合、$ a_t = An ^ 2x ^ n $
例
不均一な漸化式を$ F_n = AF_ {n–1} + BF_ {n-2} + f（n）$とし、標数根$ x_1 = 2 $および$ x_2 = 5 $とします。$ f（n）$のさまざまな可能な値の試行解は、次のとおりです。
| f（n） | トライアルソリューション |
|---|---|
| 4 | A |
| 5.2 n | An2 n |
| 8.5 n | An5 n |
| 4 n | A4 n |
| 2n 2 + 3n + 1 | 2 + Bnの+ C |
Problem
漸化式$ F_n = 3F_ {n-1} + 10F_ {n-2} + 7.5 ^ n $を解きます。ここで、$ F_0 = 4 $および$ F_1 = 3 $
Solution
これは線形の非同次関係であり、関連する同次方程式は$ F_n = 3F_ {n-1} + 10F_ {n-2} $および$ f（n）= 7.5 ^ n $です。
関連する同次関係の特性方程式は次のとおりです。
$$ x ^ 2-3x -10 = 0 $$
または、$（x-5）（x + 2）= 0 $
または、$ x_1 = 5 $および$ x_2 = -2 $
したがって、$ a_h = a.5 ^ n + b。（-2）^ n $です。ここで、aとbは定数です。
$ f（n）= 7.5 ^ n $、つまり$ cx ^ n $の形式であるため、atの妥当な試行解は$ Anx ^ n $になります。
$ a_t = Anx ^ n = An5 ^ n $
解を漸化式に置くと、次のようになります。
$ An5 ^ n = 3A（n – 1）5 ^ {n-1} + 10A（n – 2）5 ^ {n-2} + 7.5 ^ n $
両側を$ 5 ^ {n-2} $で割ると、次のようになります。
$ An5 ^ 2 = 3A（n-1）5 + 10A（n-2）5 ^ 0 + 7.5 ^ 2 $
または、$ 25An = 15An-15A + 10An-20A + 175 $
または、$ 35A = 175 $
または、$ A = 5 $
したがって、$ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $
漸化式の解は次のように書くことができます-
$ F_n = a_h + a_t $
$ = a.5 ^ n + b。（-2）^ n + n5 ^ {n + 1} $
$ F_0 = 4 $および$ F_1 = 3 $の値を入力すると、上記の式では、$ a = -2 $および$ b = 6 $が得られます。
したがって、解は次のようになります。
$ F_n = n5 ^ {n + 1} + 6。（-2）^ n -2.5 ^ n $
関数の生成
Generating Functions シーケンスの各項が形式的べき級数の変数xの係数として表されるシーケンスを表します。
数学的には、無限シーケンスの場合、たとえば$ a_0、a_1、a_2、\ dots、a_k、\ dots、$の場合、母関数は次のようになります。
$$ G_x = a_0 + a_1x + a_2x ^ 2 + \ does + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k $$
いくつかの応用分野
母関数は次の目的で使用できます-
さまざまなカウントの問題を解決するため。たとえば、Rsを変更する方法の数。Rs.1、Rs.2、Rs.5、Rs.10、Rs.20、Rs.50の紙幣を含む100紙幣
漸化式を解くため
いくつかの組み合わせのアイデンティティを証明するため
シーケンスの項の漸近式を見つけるため
Problem 1
$ a_k = 2 $および$ a_k = 3k $のシーケンス$ \ lbrace {a_k} \ rbrace $の母関数は何ですか？
Solution
$ a_k = 2 $の場合、母関数、$ G（x）= \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ dots $
$ a_ {k} = 3kの場合、G（x）= \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ does \ dots $
Problem 2
無限級数の母関数は何ですか。$ 1、1、1、1、\ dots $？
Solution
ここで、$ a_k = 1 $、$ 0 \ le k \ le \ infty $
したがって、$ G（x）= 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {（1-x）} $
いくつかの便利な母関数
$ a_k = a ^ {k}の場合、G（x）= \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ dots \ dots \ dots = 1 /（1-ax）$
$ a_ {k} =（k + 1）の場合、G（x）= \ sum_ {k = 0} ^ {\ infty}（k + 1）x ^ {k} = 1 + 2x + 3x ^ {2} \ dots \ dots \ dots = \ frac {1} {（1-x）^ {2}} $
$ a_ {k} = c_ {k} ^ {n}の場合、G（x）= \ sum_ {k = 0} ^ {\ infty} c_ {k} ^ {n} x ^ {k} = 1 + c_ {1} ^ {n} x + c_ {2} ^ {n} x ^ {2} + \非常に\ドット\ドット\ドット+ x ^ {2} =（1 + x）^ {n} $
$ a_ {k} = \ frac {1} {k！}の場合、G（x）= \ sum_ {k = 0} ^ {\ infty} \ frac {x ^ {k}} {k！} = 1 + x + \ frac {x ^ {2}} {2！} + \ frac {x ^ {3}} {3！} \ dots \ dots \ dots = e ^ {x} $