112年 - 112 國立嘉義大學_碩士班招生考試試題_資訊工程學系：離散數學#144118

(a) Homogeneous recurrence relation: (n is the integer variable) \[ a_n - 6a_{n-1} = -8a_{n-2}, \quad n > 1, a_0 = 4, a_1 = 13; \]

(b) Nonhomogeneous recurrence relation: \[a_n = 4a_{n-1} + 8n > 1, n > 0, a_0 = 2;\]

(a) Please show the shortest path. The path should be represented by tracing a sequence of visited vertices, such as (a, b, f, z). (10%)

(b) Please evaluate the length of the shortest path. (10%)

(a) Is relation R antisymmetric? (5%)

(b) Is relation R irreflexive? (5%)

4. Use mathematical induction to prove
\[ 2 - 2 \times 9 + 2 \times 9^2 - \cdots + 2 \times (-9)^n = \frac{1 - (-9)^{n+1}}{5} \]
whenever ? is a nonnegative integer. (10%)

(a) Please describe the binary relation of partial ordering by using the following example: let T be a set of positive integers, and let R be a binary relation on T such that (x, y) for x, y ∈ T is in R if ? divides y.
(5%)

(b) The binary relation can be represented graphically. Represent the elements in Tby points and use arrows to represent the ordered pairs in R. Please show that the above-mentioned directed graph has no cycles if deleting the self-loops from the poset (T, R). (5%)

(c) Please draw Hasse diagrams for the posets (T₁,R ) and (T₂,R) where
\(T_1 = \{8, 168, 4, 112, 28\}\), \(T_2 = \{9, 6, 72, 1512, 108, 3, 36\}\) and \(R\) is
defined above. Please explain whether they are lattices or not. (10%)

(a) Please describe how to calculateb⁸³ mod ? (i.e., the exponent e =(83)₁₀: decimal representation) by the above algorithm and explain it is correct. (10%)

(b) If there is a ?-bit exponent ? with \[ \left\lceil \frac{k}{2} \right\rceil \] bits of “1”, where ⌈ ⌉ denotes a
ceiling function. How many times of multiplications in this algorithm to
calculate b^e mod m. Please explain your answer. (10%)