[試題] 110-2 呂育道 離散數學 第二次期中考
課程名稱︰離散數學
課程性質︰資工系大一選修
課程教師︰呂育道
開課學院：
開課系所︰
考試日期（年月日）︰
考試時限（分鐘）： 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://www.ptt.cc/bbs/NTU-Exam/M.1655311173.A.382.html
※ 編輯: sN0w374625cS (114.37.182.241 臺灣), 06/16/2022 00:53:54
推
06/16 08:50,
1年前
, 1F
06/16 08:50, 1F