深圳酒店网站建设,中立建设集团有限公司网站,怎么制作一个简单的网页,二维码生成器支持微信扫码目录 1. 递推关系建立2. 常系数齐次递推关系的求解3. 常系数非齐次递推关系的求解4. 迭代法 1. 递推关系建立
给定一个数的序列 f ( 0 ) , f ( 1 ) , . . . , f ( n ) , . . . , f (0), f(1), ..., f(n ),... , f(0),f(1),...,f(n),..., 若存在整数 n 0 n_0 n0 #xff… 目录 1. 递推关系建立2. 常系数齐次递推关系的求解3. 常系数非齐次递推关系的求解4. 迭代法 1. 递推关系建立
给定一个数的序列 f ( 0 ) , f ( 1 ) , . . . , f ( n ) , . . . , f (0), f(1), ..., f(n ),... , f(0),f(1),...,f(n),..., 若存在整数 n 0 n_0 n0 使当 n ≥ n 0 n≥ n_0 n≥n0 时,可以用等号或大于号、小于号将 f ( n ) f (n) f(n) 与前面的某些项 f ( i ) ( 0 ≤ i n ) f (i) (0 ≤ i n) f(i)(0≤in) 联系起来这样的式子称作递推关系 建立递推关系的步骤如下:
找第 n 项与其前面最近几项的关系获得最前面几项的具体值即初值 习题1、 n 位四进制数中有偶数个 0 的序列共有多少个 解: 设 f ( n ) f(n) f(n) 表示 n 位四进制数中有偶数个 0 的序列它可由两部分生成: (1) 在 n −1位四进制数中有偶数个 0 的序列上再添一位非 0即 1,2,3的数可产生 3 f ( n − 1 ) 3f (n −1) 3f(n−1) 个 (2) 在 n −1位四进制数中有奇数个 0 的序列上再添一位 0可产生 4 n − 1 − f ( n − 1 ) 4^{n-1}-f(n-1) 4n−1−f(n−1) 个 由加法原则 f ( n ) 3 f ( n − 1 ) 4 n − 1 − f ( n − 1 ) 4 n − 1 2 f ( n − 1 ) f(n)3f(n-1)4^{n-1}-f(n-1)4^{n-1}2f(n-1) f(n)3f(n−1)4n−1−f(n−1)4n−12f(n−1)显然 f ( 1 ) 3 f(1)3 f(1)3 所以构成带初值的递推关系 { f ( n ) 4 n − 1 2 f ( n − 1 ) f ( 1 ) 3 \left\{\begin{matrix} f(n)4^{n-1}2f(n-1)\\ f(1)3 \end{matrix}\right. {f(n)4n−12f(n−1)f(1)3 习题2、 1×n 棋盘用红、白、蓝 3 种颜色着色不允许相邻两格都着红色求着色方案数 解: 设 f ( n ) f (n ) f(n) 表示满足条件的着色方案数。在该棋盘上着色其方案可分成如下 2 类 (1) 第一个格子着白/蓝色余下的是1x(n-1)的棋盘它所满足条件的着色方案数是: 2 f ( n − 1 ) 2f(n-1) 2f(n−1) (2) 第一个格子着红色第二个格子着白/蓝色余下1x(n-2)的棋盘着色方案数是: 2 f ( n − 2 ) 2f(n-2) 2f(n−2) 故总的着色方案数为 { f ( n ) 2 f ( n − 1 ) 2 f ( n − 2 ) f ( 1 ) 3 , f ( 2 ) 8 \left\{\begin{matrix} f(n)2f(n-1)2f(n-2)\\ f(1)3,f(2)8 \end{matrix}\right. {f(n)2f(n−1)2f(n−2)f(1)3,f(2)8 给定递推关系 f ( n ) c 1 ( n ) f ( n − 1 ) c 2 ( n ) f ( n − 2 ) . . . c k ( n ) f ( n − k ) g ( n ) f(n)c_1(n)f(n-1)c_2(n)f(n-2)...c_k(n)f(n-k)g(n) f(n)c1(n)f(n−1)c2(n)f(n−2)...ck(n)f(n−k)g(n)其中 c k ( n ) ≠ 0 c_k(n)\ne 0 ck(n)0则称该关系为 { f ( n ) } \{ f(n)\} {f(n)} 的 k 阶线性递推关系 如果 g ( n ) 0 g(n)0 g(n)0 则称之为齐次
2. 常系数齐次递推关系的求解 f ( n ) c 1 ( n ) f ( n − 1 ) c 2 ( n ) f ( n − 2 ) . . . c k ( n ) f ( n − k ) f(n)c_1(n)f(n-1)c_2(n)f(n-2)...c_k(n)f(n-k) f(n)c1(n)f(n−1)c2(n)f(n−2)...ck(n)f(n−k) 方程 x k − c 1 x k − 1 − c 2 x k − 2 − . . . − c k 0 x^k-c_1x^{k-1}-c_2x^{k-2}-...-c_k0 xk−c1xk−1−c2xk−2−...−ck0是上述递推关系的的特征方程它的 k k k 个根 q 1 , q 2 , . . . , q k q_1,q_2,...,q_k q1,q2,...,qk可能有重根叫作该递推关系的特征根其中 q i ( i 1 , 2 , . . . , k ) q_i (i1,2,... , k ) qi(i1,2,...,k)是复数。 定理 2.1设 q q q 是非零复数当且仅当 q 是它的特征根 f ( n ) q n f(n)q^n f(n)qn 是递推关系的解 定理 2.2如果 h 1 ( n ) , h 2 ( n ) h_1(n),h_2(n) h1(n),h2(n)都是递推关系的解 b 1 b_1 b1 b 2 b_2 b2是常数则 b 1 h 1 ( n ) b 2 h 2 ( n ) b_1h_1(n)b_2h_2(n) b1h1(n)b2h2(n)也是递推关系的解 定理 2.3设 q 1 , q 2 , . . . , q k q_1,q_2,...,q_k q1,q2,...,qk是递推关系的 k 个互不相等的特征根 b 1 b_1 b1 b 2 b_2 b2是常数则 f ( n ) b 1 q 1 n b 2 q 2 n . . . b k q k n f(n)b_1q_1^nb_2q_2^n...b_kq_k^n f(n)b1q1nb2q2n...bkqkn 是递推关系通解 习题3、 求解递推关系 { f ( n ) 7 f ( n − 1 ) − 12 f ( n − 2 ) f ( 0 ) 2 , f ( 1 ) 7 \left\{\begin{matrix} f(n)7f(n-1)-12f(n-2)\\ f(0)2,f(1)7 \end{matrix}\right. {f(n)7f(n−1)−12f(n−2)f(0)2,f(1)7 解: 先求这个递推关系的通解。其特征方程为 x 2 − 7 x 12 0 x^2-7x120 x2−7x120解这个方程得 x 1 4 , x 2 3 x_14,x_23 x14,x23所以通解为 f ( n ) c 1 ⋅ 4 n c 2 ⋅ 3 n f(n)c_1\cdot 4^nc_2 \cdot 3^n f(n)c1⋅4nc2⋅3n 带入初值确定 c 1 , c 2 c_1,c_2 c1,c2得 { c 1 c 2 2 4 c 1 3 c 2 7 \left\{\begin{matrix} c_1c_22\\ 4c_13c_27 \end{matrix}\right. {c1c224c13c27 得 c 1 1 , c 2 1 c_11 ,c_21 c11,c21 所以通解为 f ( n ) 4 n 3 n f(n)4^n3^n f(n)4n3n 习题4、 求解递推关系 { f ( n ) f ( n − 1 ) 9 f ( n − 2 ) − 9 f ( n − 3 ) f ( 0 ) 0 , f ( 1 ) 1 , f ( 2 ) 2 \left\{\begin{matrix} f(n)f(n-1)9f(n-2)-9f(n-3)\\ f(0)0,f(1)1,f(2)2 \end{matrix}\right. {f(n)f(n−1)9f(n−2)−9f(n−3)f(0)0,f(1)1,f(2)2 解: 先求这个递推关系的通解。其特征方程为 x 3 − x 2 − 9 x 9 0 x^3-x^2-9x90 x3−x2−9x90解这个方程得 x 1 1 , x 2 3 , x 3 − 3 x_11,x_23,x_3-3 x11,x23,x3−3所以通解为 f ( n ) c 1 ⋅ 1 n c 2 ⋅ 3 n c 3 ⋅ ( − 3 ) n f(n)c_1\cdot 1^nc_2 \cdot 3^nc_3\cdot (-3)^n f(n)c1⋅1nc2⋅3nc3⋅(−3)n 带入初值确定 c 1 , c 2 , c 3 c_1,c_2,c_3 c1,c2,c3得 { c 1 c 2 c 3 0 c 1 3 c 2 − 3 c 3 1 c 1 9 c 2 9 c 3 2 \left\{\begin{matrix} c_1c_2c_30\\ c_13c_2-3c_31\\ c_19c_29c_32 \end{matrix}\right. ⎩ ⎨ ⎧c1c2c30c13c2−3c31c19c29c32 得 c 1 − 1 4 , c 2 1 3 , c 3 − 1 12 c_1-\frac{1}{4} ,c_2\frac{1}{3},c_3-\frac{1}{12} c1−41,c231,c3−121 所以通解为 f ( n ) − 1 4 ⋅ 1 n 1 3 ⋅ 3 n − 1 12 ⋅ ( − 3 ) n f(n)-\frac{1}{4}\cdot 1^n\frac{1}{3} \cdot 3^n-\frac{1}{12}\cdot (-3)^n f(n)−41⋅1n31⋅3n−121⋅(−3)n 定理 2.4设 q 1 , q 2 , . . . , q k q_1,q_2,...,q_k q1,q2,...,qk是递推关系的全部不同的特征根其重数分别为 e 1 , e 2 , . . . , e t e_1,e_2,...,e_t e1,e2,...,et ( e 1 e 2 . . . e t k ) (e_1e_2...e_tk) (e1e2...etk)则递推关系的通解为 f ( n ) f 1 ( n ) f 2 ( n ) . . . f t ( n ) f(n)f_1(n)f_2(n)...f_t(n) f(n)f1(n)f2(n)...ft(n)其中 f i ( n ) ( b i 1 b i 2 n . . . b i e i n e i − 1 ) ⋅ q i n ( 1 ≤ i ≤ t ) f_i(n)(b_{i_1}b_{i_2}n...b_{i_{e_i}}n^{e_i-1})\cdot q_i^n \quad(1\le i\le t) fi(n)(bi1bi2n...bieinei−1)⋅qin(1≤i≤t) 习题5、 求解递推关系 { f ( n ) 3 f ( n − 2 ) − 2 f ( n − 3 ) ( n ≥ 3 ) f ( 0 ) 1 , f ( 1 ) 0 , f ( 2 ) 0 \left\{\begin{matrix} f(n)3f(n-2)-2f(n-3)\quad (n\ge3)\\ f(0)1,f(1)0,f(2)0 \end{matrix}\right. {f(n)3f(n−2)−2f(n−3)(n≥3)f(0)1,f(1)0,f(2)0 解: 先求这个递推关系的通解。其特征方程为 x 3 − 3 x 2 0 x^3-3x20 x3−3x20解这个方程得 x 1 1 , x 2 1 , x 3 − 2 x_11,x_21,x_3-2 x11,x21,x3−2所以通解为 f ( n ) c 1 ⋅ 1 n c 2 n ⋅ 1 n c 3 ⋅ ( − 2 ) n f(n)c_1\cdot 1^nc_2n \cdot 1^nc_3\cdot (-2)^n f(n)c1⋅1nc2n⋅1nc3⋅(−2)n 带入初值确定 c 1 , c 2 , c 3 c_1,c_2,c_3 c1,c2,c3得 { c 1 c 3 1 c 1 c 2 − 2 c 3 0 c 1 2 c 2 4 c 3 0 \left\{\begin{matrix} c_1c_31\\ c_1c_2-2c_30\\ c_12c_24c_30 \end{matrix}\right. ⎩ ⎨ ⎧c1c31c1c2−2c30c12c24c30 得 c 1 8 9 , c 2 − 2 3 , c 3 1 9 c_1\frac{8}{9} ,c_2-\frac{2}{3},c_3\frac{1}{9} c198,c2−32,c391 所以通解为 f ( n ) 8 9 ⋅ 1 n − 2 3 n ⋅ 1 n 1 9 ⋅ ( − 2 ) n 8 9 − 2 3 n 1 9 ⋅ ( − 2 ) n f(n)\frac{8}{9}\cdot 1^n-\frac{2}{3}n \cdot 1^n\frac{1}{9}\cdot (-2)^n\frac{8}{9}-\frac{2}{3}n\frac{1}{9}\cdot (-2)^n f(n)98⋅1n−32n⋅1n91⋅(−2)n98−32n91⋅(−2)n 3. 常系数非齐次递推关系的求解 f ( n ) c 1 ( n ) f ( n − 1 ) c 2 ( n ) f ( n − 2 ) . . . c k ( n ) f ( n − k ) g ( n ) f(n)c_1(n)f(n-1)c_2(n)f(n-2)...c_k(n)f(n-k)g(n) f(n)c1(n)f(n−1)c2(n)f(n−2)...ck(n)f(n−k)g(n)对应的齐次递推关系为 f ( n ) c 1 ( n ) f ( n − 1 ) c 2 ( n ) f ( n − 2 ) . . . c k ( n ) f ( n − k ) f(n)c_1(n)f(n-1)c_2(n)f(n-2)...c_k(n)f(n-k) f(n)c1(n)f(n−1)c2(n)f(n−2)...ck(n)f(n−k) 定理 3.1k 阶常系数线性非齐次递推关系的通解是递推关系的特解加上其相应的齐次递推关系的通解。即非齐次递推关系的解 特解 齐次方程通解 习题6、 求解递推关系 { f ( n ) 4 f ( n − 1 ) − 3 f ( n − 2 ) 3 n ( n ≥ 2 ) f ( 0 ) 1 , f ( 1 ) 2 \left\{\begin{matrix} f(n)4f(n-1)-3f(n-2)3^n\quad (n\ge2)\\ f(0)1,f(1)2 \end{matrix}\right. {f(n)4f(n−1)−3f(n−2)3n(n≥2)f(0)1,f(1)2 解: 先求这个递推关系的通解。其特征方程为 x 2 − 4 x 3 0 x^2-4x30 x2−4x30解这个方程得 x 1 1 , x 2 3 x_11,x_23 x11,x23因为3是特征方程的一重根所以该递推关系的非齐次特解为 a n 3 n an3^n an3n。将其代入递推关系得 a n 3 n 4 a ( n − 1 ) 3 n − 1 − 3 a ( n − 2 ) 3 n − 2 3 n an3^n4a(n-1)3^{n-1}-3a(n-2)3^{n-2}3^n an3n4a(n−1)3n−1−3a(n−2)3n−23n化简得 a 3 2 a\frac{3}{2} a23特解为 f ′ ( n ) 3 2 n 3 n f(n)\frac{3}{2}n3^n f′(n)23n3n 而相应齐次递推关系的通解为 f ′ ′ ( n ) c 1 ⋅ 1 n c 2 n ⋅ 3 n f(n)c_1\cdot 1^nc_2n \cdot 3^n f′′(n)c1⋅1nc2n⋅3n 通解为 f ( n ) f ′ ( n ) f ′ ′ ( n ) c 1 c 2 ⋅ 3 n 3 2 n 3 n f(n)f(n)f(n)c_1c_2\cdot 3^n\frac{3}{2}n3^n f(n)f′(n)f′′(n)c1c2⋅3n23n3n带入初值确定 c 1 , c 2 c_1,c_2 c1,c2得 { c 1 c 2 1 c 1 3 c 2 9 2 2 \left\{\begin{matrix} c_1c_21\\ c_13c_2\frac{9}{2}2 \end{matrix}\right. {c1c21c13c2292 得 c 1 11 4 , c 2 − 7 4 c_1\frac{11}{4} ,c_2-\frac{7}{4} c1411,c2−47 所以通解为 f ( n ) 11 4 − 7 4 ⋅ 3 n 3 2 n 3 n f(n)\frac{11}{4}-\frac{7}{4}\cdot3^n\frac{3}{2}n3^n f(n)411−47⋅3n23n3n 习题7、 求解递推关系 { f ( n ) f ( n − 1 ) n 2 f ( 1 ) 1 , f ( 2 ) 5 , f ( 3 ) 14 \left\{\begin{matrix} f(n)f(n-1)n^2\\ f(1)1,f(2)5,f(3)14 \end{matrix}\right. {f(n)f(n−1)n2f(1)1,f(2)5,f(3)14 解: 先求这个递推关系的通解。其特征方程为 x − 1 0 x-10 x−10解这个方程得 x 1 x1 x1因为1是特征方程的一重根所以该递推关系的非齐次特解为 n 1 ( b 2 n 2 b 1 n 1 b 0 ) n^1(b_2n^2b_1n^1b_0) n1(b2n2b1n1b0)。将其代入递推关系得 n 1 ( b 2 n 2 b 1 n 1 b 0 ) ( n − 1 ) ( b 2 ( n − 1 ) 2 b 1 ( n − 1 ) b 0 ) n 2 n^1(b_2n^2b_1n^1b_0)(n-1)(b_2(n-1)^2b_1(n-1)b_0)n^2 n1(b2n2b1n1b0)(n−1)(b2(n−1)2b1(n−1)b0)n2比较系数可得 { b 1 − 3 b 2 b 1 1 b 0 3 b 2 − 2 b 1 b 0 0 − b 2 b 1 − b 0 \left\{\begin{matrix} b_1-3b_2b_11\\ b_03b_2-2b_1b_0\\ 0-b_2b_1-b_0 \end{matrix}\right. ⎩ ⎨ ⎧b1−3b2b11b03b2−2b1b00−b2b1−b0解得 { b 0 1 / 6 b 1 1 / 2 b 2 1 / 3 \left\{\begin{matrix} b_01/6\\ b_11/2\\ b_21/3 \end{matrix}\right. ⎩ ⎨ ⎧b01/6b11/2b21/3 特解为 f ′ ( n ) n ( 1 3 n 2 1 2 n 1 6 ) f(n)n(\frac{1}{3}n^2\frac{1}{2}n\frac{1}{6}) f′(n)n(31n221n61)而相应齐次递推关系的通解为 f ′ ′ ( n ) c 1 ⋅ 1 n f(n)c_1\cdot 1^n f′′(n)c1⋅1n 通解为 f ( n ) f ′ ( n ) f ′ ′ ( n ) c 1 ⋅ 1 n n ( 1 3 n 2 1 2 n 1 6 ) f(n)f(n)f(n)c_1\cdot 1^nn(\frac{1}{3}n^2\frac{1}{2}n\frac{1}{6}) f(n)f′(n)f′′(n)c1⋅1nn(31n221n61)带入初值确定 c 1 c_1 c1得 c 1 1 ⋅ ( 1 3 1 2 1 6 ) 1 c_11\cdot(\frac{1}{3}\frac{1}{2}\frac{1}{6})1 c11⋅(312161)1 得 c 1 0 c_10 c10 所以通解为 f ( n ) n ( 1 3 n 2 1 2 n 1 6 ) 1 6 n ( n 1 ) ( 2 n 1 ) f(n)n(\frac{1}{3}n^2\frac{1}{2}n\frac{1}{6})\frac{1}{6}n(n1)(2n1) f(n)n(31n221n61)61n(n1)(2n1) 4. 迭代法
但对于某些非线性的递推关系不存在求解的公式因此不能用上述方法。 碰到此类问题不妨尝试用迭代归纳法来求解。
