Discrete Mathematics Answers

Use generating functions to solve the recurrence relation an = 4a_n−1 − 4a_n−2 +n²

, where a₀ = 2, a₁ = 5.

List the first 10 terms of each of these sequences.

a) the sequence that begins with 2 and in which each

successive term is 3 more than the preceding term

b) the sequence that lists each positive integer three

times, in increasing order

c) the sequence that lists the odd positive integers in in-

creasing order, listing each odd integer twice

d) the sequence whose nth term is n! − 2n

e) the sequence that begins with 3, where each succeed-

ing term is twice the preceding term

f ) the sequence whose first term is 2, second term is 4,

and each succeeding term is the sum of the two pre-

ceding terms

g) the sequence whose nth term is the number of bits

in the binary expansion of the number n (defined in

Section 4.2)

h) the sequence where the nth term is the number of let-

ters in the English word for the index n

Suppose a recurrence relation

an=4an−1−4an−2

where a1=14 and a2=40

can be represented in explicit formula, either as:

Formula 1:

an=pxn+qnxn

or

Formula 2:

an=pxn+qyn

where

x

and

y

are roots of the characteristic equation.

Determine

p

and

q

.

You are required to prepare a 15-minute presentation aimed towards new students engaged under a technology company’s graduate scheme.

Your presentation will include evidence of:

1. An explanation that adequately explains why group theory is taught to computing students.

2. The application of group theory within public key cryptography. All work should be appropriately and accurately referenced

Given that 𝐺 = {𝑎 ∈ ℝ|𝑎 ≠ −1} and 𝑎 ∗ 𝑏 = 𝑎 + 𝑏 + 𝑎𝑏, show that (𝐺, ∗) is indeed a group.

When considering the set of all the natural numbers (ℕ), show whether the mathematical operations of addition, subtraction, multiplication and division are: (a) Associative (b) Commutative.

State the Pigeonhole Principle. A chess player wants to prepare for a championship match by playing

some practice games in 77 days. She wants to play at least one game a day but no more than 132

games altogether. Prove that there is a period of consecutive days within which she plays exactly 21

games

State the Pigeonhole Principle. In a result sheet of a list of 60 students, each marked “Pass” or “Fail

“. There are 35 students pass. Show that there are at least two students pass in the list exactly nine

students apart. (for example students at numbered 2 and 11 or at numbered 50 and 59 satisfy the

condition).

Consider a recurrence relation an = an-1 - 3an-2 for n = 1,2,3,4,… with initial conditions a1 = 3 and a2 = 5. Calculate a5.

Consider a recurrence relation an = -3an-1 + n for n = 1,2,3,4,… with initial conditions a1 = 3. Calculate a3.