CALCU-MATH1043 Discrete Mathematics4. Obtain the T

Generated Graph

Solution by Steps

step 1

Identify the dominant term in the function

step 2

The dominant term is

5 n e^{n}

because it grows faster than

n^{100}

,

3 e^{n}

, and

\log(n)

step 3

Therefore,

f(n) = \Theta(n e^n)

# (b)

g(n)=(4 n-1)^{2}(n-3)

step 1

Expand the function to find the dominant term

step 2

(4n-1)^2 = 16n^2 - 8n + 1

and

(16n^2 - 8n + 1)(n-3) = 16n^3 - 48n^2 - 8n^2 + 24n + n - 3 = 16n^3 - 56n^2 + 25n - 3

step 3

The dominant term is

16n^3

step 4

Therefore,

g(n) = \Theta(n^3)

# (c)

h(n)=\frac{n^{3} \log (n)+\log (n)+100 e^{-n}}{n^{2}+2 n+1}

step 1

Simplify the function by dividing the numerator and the denominator by

n^2

step 2

h(n) = \frac{n \log(n) + \frac{\log(n)}{n^2} + \frac{100 e^{-n}}{n^2}}{1 + \frac{2}{n} + \frac{1}{n^2}}

step 3

As

n \to \infty

, the dominant term in the numerator is

n \log(n)

and in the denominator is

1

step 4

Therefore,

h(n) = \Theta(n \log(n))

Answer

(a)

\Theta(n e^n)

, (b)

\Theta(n^3)

, (c)

\Theta(n \log(n))

Question 5 # (a) Counting to come up with

2^n

step 1

Consider counting the number of ways to flip

n

coins, each of which can be heads or tails

step 2

Each coin has 2 possible outcomes, so the total number of outcomes is

2^n

# (b) Counting to come up with

\sum_{k=0}^{n} C_{k}^{n}

step 1

Consider counting the number of ways to choose

k

heads out of

n

coins

step 2

The number of ways to choose

k

heads out of

n

coins is given by the binomial coefficient

C_{k}^{n}

step 3

Summing over all possible values of

k

from 0 to

n

, we get

\sum_{k=0}^{n} C_{k}^{n}

# (c) Justification

step 1

Both parts (a) and (b) are counting the same set of outcomes (the number of ways to flip

n

coins)

step 2

Therefore,

2^n = \sum_{k=0}^{n} C_{k}^{n}

Answer

(a)

2^n

, (b)

\sum_{k=0}^{n} C_{k}^{n}

, (c)

2^n = \sum_{k=0}^{n} C_{k}^{n}

Question 6 # (a) Integer solutions for

x_{i} \geq 0

step 1

Use the stars and bars method to find the number of non-negative integer solutions

step 2

The number of solutions is given by

C(30 + 3 - 1, 3 - 1) = C(32, 2)

step 3

C(32, 2) = \frac{32 \cdot 31}{2} = 496

# (b) Integer solutions for x_{i} > 0

step 1

Use the stars and bars method to find the number of positive integer solutions

step 2

Let

x_i' = x_i - 1

so that

x_i' \geq 0

step 3

The equation becomes

x_1' + x_2' + x_3' = 27

step 4

The number of solutions is given by

C(27 + 3 - 1, 3 - 1) = C(29, 2)

step 5

C(29, 2) = \frac{29 \cdot 28}{2} = 406

# (c) Integer solutions for

x_{1} \geq 0, x_{2} \geq 1, x_{3} \geq 2

step 1

Adjust the variables to account for the constraints: let

x_2' = x_2 - 1

and

x_3' = x_3 - 2

step 2

The equation becomes

x_1 + x_2' + x_3' = 27

step 3

The number of solutions is given by

C(27 + 3 - 1, 3 - 1) = C(29, 2)

step 4

C(29, 2) = \frac{29 \cdot 28}{2} = 406

Answer

(a) 496, (b) 406, (c) 406

Key Concept

Theta notation, Counting arguments, Stars and bars method

Explanation

Theta notation helps in understanding the growth rate of functions. Counting arguments and the stars and bars method are useful in combinatorial problems to find the number of ways to distribute objects.

Generated Graph

Solution by Steps

step 1

To show that

2^n = \sum_{k=0}^{n} \binom{n}{k}

using a counting argument, we start by considering the total number of subsets of a set with

n

elements

step 2

Each element in the set can either be included in a subset or not, giving us

2

choices per element. Therefore, the total number of subsets is

2^n

step 3

Now, let's count the subsets by their sizes. A subset can have

0

elements,

1

element,

2

elements, and so on, up to

n

elements

step 4

The number of subsets with exactly

k

elements is given by the binomial coefficient

\binom{n}{k}

step 5

Summing the number of subsets of all possible sizes, we get

\sum_{k=0}^{n} \binom{n}{k}

step 6

Since both methods count the same thing (the total number of subsets of a set with

n

elements), we have

2^n = \sum_{k=0}^{n} \binom{n}{k}

Answer

2^n = \sum_{k=0}^{n} \binom{n}{k}

Key Concept

Counting Subsets

Explanation

We used two different counting methods to show that the total number of subsets of a set with

n

elements is

2^n

, which is also the sum of the binomial coefficients

\binom{n}{k}

for

k

from

0

to

n

.

Solution by Steps

step 1

To find a constant solution to the non-homogeneous part, we assume

a_n = C

where

C

is a constant

step 2

Substituting

a_n = C

into the recurrence relation

a_{n+2} - 6a_{n+1} + 9a_n = 2

, we get

C - 6C + 9C = 2

step 3

Simplifying, we have

4C = 2

, so

C = \frac{1}{2}

# Part (b)

step 1

To solve the homogeneous part

a_{n+2} - 6a_{n+1} + 9a_n = 0

, we solve the characteristic equation

r^2 - 6r + 9 = 0

step 2

The characteristic equation factors as

(r - 3)^2 = 0

, giving a repeated root

r = 3

step 3

Therefore, the general solution to the homogeneous part is

a_n = (A + Bn)3^n

, where

A

and

B

are constants

# Part (c)

step 1

The general solution to the non-homogeneous recurrence relation is the sum of the homogeneous solution and the particular solution:

a_n = (A + Bn)3^n + \frac{1}{2}

step 2

Using the initial conditions

a_0 = 1

and

a_1 = 3

, we substitute

n = 0

and

n = 1

to find

A

and

B

step 3

For

n = 0

:

1 = A \cdot 3^0 + \frac{1}{2} \Rightarrow A + \frac{1}{2} = 1 \Rightarrow A = \frac{1}{2}

step 4

For

n = 1

:

3 = (A + B)3 + \frac{1}{2} \Rightarrow 3 = \left(\frac{1}{2} + B\right)3 + \frac{1}{2} \Rightarrow 3 = \frac{3}{2} + 3B + \frac{1}{2} \Rightarrow 3 = 2 + 3B \Rightarrow 3B = 1 \Rightarrow B = \frac{1}{3}

step 5

Therefore, the particular solution is

a_n = \left(\frac{1}{2} + \frac{n}{3}\right)3^n + \frac{1}{2}

Answer

a_n = \left(\frac{1}{2} + \frac{n}{3}\right)3^n + \frac{1}{2}

Question 8 # Part (a)

step 1

K_{2,1}

can be drawn as a straight line with 3 vertices:

a

,

b

, and

1

step 2

Euler's formula for planar graphs is

V - E + F = 2

. For

K_{2,1}

,

V = 3

,

E = 2

, and

F = 1

step 3

Substituting, we get

3 - 2 + 1 = 2

, which holds true

# Part (b)

step 1

K_{2,2}

can be drawn as a square (or diamond) with vertices

a

,

b

,

1

, and

2

step 2

Euler's formula for planar graphs is

V - E + F = 2

. For

K_{2,2}

,

V = 4

,

E = 4

, and

F = 2

step 3

Substituting, we get

4 - 4 + 2 = 2

, which holds true

# Part (c)

step 1

To prove by induction that

K_{2,m}

is planar, we start with the base case

m = 1

and

m = 2

, which are planar as shown in parts (a) and (b)

step 2

Assume

K_{2,k}

is planar for some

k \geq 2

step 3

For

K_{2,k+1}

, add one more vertex to the group of

m

vertices and connect it to

a

and

b

step 4

This does not introduce any crossings, so

K_{2,k+1}

is also planar

step 5

By induction,

K_{2,m}

is planar for all positive integers

m

# Part (d)

step 1

K_{2,m}

can be drawn with vertices

a

and

b

connected to

1, 2, \ldots, m

without any crossings

# Part (e)

step 1

If

m

is odd, there is no Euler tour because each vertex must have an even degree for an Euler tour to exist

# Part (f)

step 1

If

m

is even, there is an Euler tour. One possible path is

a \rightarrow 1 \rightarrow b \rightarrow 2 \rightarrow a \rightarrow 3 \rightarrow b \rightarrow 4 \rightarrow \ldots \rightarrow a \rightarrow m \rightarrow b

Answer

(a) Euler's formula holds for

K_{2,1}

. (b) Euler's formula holds for

K_{2,2}

. (c)

K_{2,m}

is planar by induction. (d)

K_{2,m}

can be drawn without crossings. (e) No Euler tour if

m

is odd. (f) Euler tour exists if

m

is even.

Key Concept

Recurrence relations and planar graphs

Explanation

The solution involves finding particular and general solutions to recurrence relations and verifying properties of planar graphs using Euler's formula and induction.

AskSia

Plus