離散数学-漸化式

この章では、再帰的手法を使用してシーケンスを導出し、カウントの問題を解決する方法について説明します。シーケンスの項を再帰的に見つける手順は、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} $