作者sN0w374625cS (软烂)
看板NTU-Exam
标题[试题] 110-2 吕育道 离散数学 第二次期中考
时间Thu Jun 16 00:39:31 2022
课程名称︰离散数学
课程性质︰资工系大一选修
课程教师︰吕育道
开课学院:
开课系所︰
考试日期(年月日)︰
考试时限(分钟): 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/cn.aspx?n=bbs/NTU-Exam/M.1655311173.A.382.html
※ 编辑: sN0w374625cS (114.37.182.241 台湾), 06/16/2022 00:53:54
1F:推 rod24574575 : 收录资讯系! 06/16 08:50