99年國立清華大學資工所離散數學

1.

Prove that n! ≥ 2ⁿ⁻¹ for any positive integer n.

2.

Solve the recurrence equation x_n+1 − 3x_n + 2x_n−1 = 3, n ≥ 1, with x₀ = 1, x₁ = 2.

3.

Evaluate (30)¹⁶ mod 257.

4.

Solve for x in 7^x ≡ 1 (mod 29).

5.

Let Fibonacci number f₀ = 0, f₁ = 1, and f_n+2 = f_n+1 + f_n for n ≥ 0. Prove that

Use the following steps to solve the recurrent relation (n + 1)a_n+1 = a_n + (1/n!) for n ≥ 0.

6.

Let G(x) be generating function for {an} show that
       G(0) = 1 and G'(x) = G(x) + e^x.
[Note that G'(x) denotes the first derivative of G(x)]

Use the following steps to solve the recurrent relation (n + 1)a_n+1 = a_n + (1/n!) for n ≥ 0.

7.

Use calculus to show from part (a) that (e^−xG(x))' = 1 and conclude that
                  G(x) = xe^x + e^x.
[Note that (e^−xG(x))' denotes the first derivative of (e−xG(x))]

Use the following steps to solve the recurrent relation (n + 1)a_n+1 = a_n + (1/n!) for n ≥ 0.

8.

Use part (b) to find the closed form for a_n.

Let G be connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G, and Euler formula r = e − v + 2.

9.

If G is a connected planar simple graph with e edges and v vertices where v ≥ 3
and no circuit of length three, prove that e ≤ 2v − 4.

Let G be connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G, and Euler formula r = e − v + 2.

10.

Use corollary (a) to show that graph K3,3 below is non-planar.