Discrete-mathematics-recurrence-relation
離散数学-再発関係
この章では、再帰的手法がシーケンスを導出し、カウント問題の解決に使用する方法について説明します。 再帰的な方法でシーケンスの用語を見つける手順は、*再帰関係*と呼ばれます。 線形回帰関係とその解の理論を研究します。 最後に、再帰関係を解決するための生成関数を紹介します。
定義
再帰関係は、次の項が前の項の関数であるシーケンスを再帰的に定義する方程式です（$ F_i $と$ i <n $の組み合わせとして$ F_n $を表します）。
例-フィボナッチ数列-$ 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} + \という形式の回帰方程式です。ドットA_k x _ \ {nk} $（$ A_n $は定数で、$ A_k \ neq 0 $）は1次多項式としての数値のシーケンスです。
これらは、線形回帰方程式のいくつかの例です-
| Recurrence relations | Initial values | Solutions |
|---|---|---|
| Fn = Fn-1 + Fn-2 | a1 = a2 = 1 | Fibonacci number |
| Fn = Fn-1 + Fn-2 | a1 = 1, a2 = 3 | Lucas Number |
| Fn = Fn-2 + Fn-3 | a1 = a2 = a3 = 1 | Padovan sequence |
| Fn = 2Fn-1 + Fn-2 | a1 = 0, a2 = 1 | Pell number |
線形回帰関係を解決する方法
2つの順序付き線形回帰関係が-$ F_n = AF _ \ {n-1} + BF _ \ {n-2} $であり、AとBが実数であるとします。
上記の再帰関係の特性方程式は-
x ^ 2-Ax-B = 0
根を見つけるときに3つのケースが発生する可能性があります-
- ケース1 *-この方程式が$（x- x_1）（x- x_1）= 0 $として因数分解し、2つの異なる実根$ x_1 $と$ x_2 $を生成する場合、$ F_n = ax_1 ^ n + bx_2 ^ n $解決策です。 [ここで、aとbは定数です]
- ケース2 *-この方程式が$（x- x_1）^ 2 = 0 $として因数分解し、単一の実根$ x_1 $を生成する場合、$ F_n = a x_1 ^ n + bn x_1 ^ n $が解です。
- ケース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））$は解です。
- 問題1 *
再帰関係を解く$ F_n = 5F _ \ {n-1}-6F _ \ {n-2} $ここで、$ F_0 = 1 $および$ F_1 = 4 $
溶液
回帰関係の特性方程式は-
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 \ and \ 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
- 問題2 *
再帰関係を解く-$ F_n = 10F _ \ {n-1}-25F _ \ {n-2} $ここで、$ F_0 = 3 $および$ F_1 = 17 $
溶液
回帰関係の特性方程式は-
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 $
- 問題3 *
再帰関係$ F_n = 2F _ \ {n-1}-2F _ \ {n-2} $を解きます。ここで$ F_0 = 1 $および$ F_1 = 3 $
溶液
回帰関係の特性方程式は-
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) | Trial solutions |
|---|---|
| 4 | A |
| 5.2n | An2n |
| 8.5n | An5n |
| 4n | A4n |
| 2n2+3n+1 | An2+Bn+C |
問題
再帰関係を解く$ F_n = 3F _ \ {n-1} + 10F _ \ {n-2} + 7.5 ^ n $ここで、$ F_0 = 4 $および$ F_1 = 3 $
溶液
これは線形の非同次関係であり、関連する同次方程式は$ 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 $なので、つまり $ c.x ^ 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 $
関数を生成する
- 生成関数*は、シーケンスの各項が正式なべき級数の変数xの係数として表されるシーケンスを表します。
数学的には、無限シーケンス、たとえば$ a_0、a_1、a_2、\ dots、a_k、\ dots、$の場合、生成関数は-
G_x = a_0 + a_1x + a_2x ^ 2 + \ dots + 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ノート
- 再発関係を解決するために
- 組み合わせアイデンティティのいくつかを証明するために
- シーケンスの項の漸近式を見つけるため
- 問題1 *
$ a_k = 2 $および$ a_k = 3k $のシーケンス$ \ lbrace \ {a_k} \ rbrace $の生成関数は何ですか？
溶液
$ 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} + \ dots \ dots $
- 問題2 *
無限級数の生成関数は何ですか？ $ 1、1、1、1、\ dots $？
溶液
ここでは、$ 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} + \ dots \ dots \ dots + 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} $
