課程名稱︰離散數學 課程性質︰資工系大一選修 課程教師︰呂育道 開課學院： 開課系所︰ 考試日期（年月日）︰ 考試時限（分鐘）： 180 mins 試題 : 1. Determine the sequence whose generating function is f(x) = x^3/(1 - x^2) Ans: It suffices to expand the generating function as follows: x^3 + x^5 + x^7 + ... Hence the sequence is 0,0,0,1,0,1,0,1,.... 2. Calculate C(-2, i) Ans: (-1)^i * (i + 1) 3. Assume x_1, x_2, . . . , x_n >= 0. Use the generating function to determine t number of integer solutions to x_1 + 2 * x_2 + 뜠뜠뜠+ n * x_n = n. Ans: See pp. 518–519 of the lecture notes. 4. Solve the recurrence relation f(n + 1) = f(n) * f(n - 1) with f(0) = 1, f(1 ) = 2. Ans: Let g(n) = log_2 (f(n)). Then g(n+1) = g(n)+g(n-1) with g(0) = 0 and g(1) = Hence f(n) = 2^{F_n} where F_n denotes the Binet formula. 5. Let n be any positive integer. Show that (1 - 4x)^{-1/2} generates the sequence C(2n, n). Ans: 略 6. Solve the recurrence relation (a_{n+2})^2 - 5 * (a_{n+1})^2 + 4 * (a_n)^2 = 0 with a_0 = 4 and a_1 =13. Ans: Take b_n = (a_n)^2 with b_0 = 16 and b_1 = 169. It is equivalent to solving the recurrence relation b_{n+2} - 5 * b_{n+1} + 4 * b_n =0. Its genera l solution is b_n = A 휠1^n + B휠4^n. It is easy to determine the coefficient A and B by imposing the initial conditions. The solution is b_n = 51 휠4^n 35. Finally, an = sqrt(b_n). 7. Solve the recurrence relation an a_n - a_{n - 1} = 3 * n^2 with a_0 = 7. Ans: 7 + n * (n + 1) * (2n + 1) / 2 8. Use the method of undetermined coefficients to solve the recurrence relatio n a_{n+2} 6 * a_{n+1} +9 * a_n = 3 휲^n + 7 휠3^n with a_0 =1 and a_1 =4. Ans: -2 * 3^n + 17/18 * n * 3^n + 3 * 2^n + 7/18 * n^2 * 3^n 9. Use the method of generating functions to solve the recurrence relation a_{n+2} * a_{n+1} +6 * a_n =2 with a_0 =3 and a_1 =7. Ans: a_n = 2 휠3^n + 1 10. Recall that E_m denotes the number of elements in S that satisfy exactly m o the t conditions. Express S_r, where m >= r, in terms of E_r,E_{r+1},…, E_t.(Recall that S_k = \sum_{1 <= i_1 < i_2 < 毽뜠< i_k <= t} N(c_{i_1} c_{i_2} 毽搾_{i_k}), where c_1, c_2,…,c_t are the conditions.) Ans: S_r = \sum_{m = r}^t C(m, r) * E_m --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.182.241 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1655311173.A.382.html ※ 編輯: sN0w374625cS (114.37.182.241 臺灣), 06/16/2022 00:53:54