Question 1

Part 1)

Consider this recursive definition of a set S:

Basis Step:

(1, 5) ∈ S and (3, 7) ∈ S

Recursive Step:

If (a, b) ∈ S then (3a + 1, 3b − 7) ∈ S

If (a, b) ∈ S and (c, d) ∈ S then (2a + d, 2b + c) ∈ S

Prove by structural induction that for any (x, y) ∈ S, x + 4 = y

Part 2)

Based on the result from Part 1, what can we say about (1000, 1004)? Briefly explain.

Question 2

Show your work for all parts.

Part 1)

Solve the following recurrence together with the given initial conditions:

an = a_n-1 + 1/4 a_n-2; a₀ = 0, a₁ = 3

Part 2)

Consider the following sequence:

a_n = 2ⁿ + 3ⁿ + 4ⁿ

We can express this sequence as a recurrence of the form: a_n =c₁ a_n-1+ c₂ a_n-2+ c₃a_n-3

What are the values of c1, c2, and c3?

What initial conditions do we need for the recurrence?

Question 3:

In attached file.

"Is this question part of your assignment? We Can Help!"