1.

Consider the difference equation

Compute several terms. Do you see a pattern? Can you prove it?

2.

Consider the same recurrence as in [1], but now let a ₀ and a ₁ be arbitrary. What happens? Can you prove it?

3.

Consider the difference equation a _{n +2}= 5 a _{n +1} ?6 a _n. Compute the first 6 terms if:

1. a ₀=1, a ₁=2

2. a ₀=5, a ₁=10

3. a ₀=1, ? ₁ =3

4. a ₀=2, a ₁=5

5. a ₀=0, a ₁=1.

Do you see a pattern? Can you prove it?

4.

In [4, Section 5.2], you were asked to find a formula relating E _{2 n} and E _n for Algorithm SEQ-SEARCH. Use that formula and the condition E ₁=1 to find and prove an explicit formula for E _n when n is a power of 2. (This may seem silly, since we already found a formula for E _n for any n, but it provides more practice, and it previews a powers of 2 approach that is very important in Section 5.8.)

5.

Use Eq. (2), Section 5.2, to find a recurrence relating E _{n +2} to E _n . Use this recurrence to find and prove an explicit formula for E _{2 n} .

6.

Suppose that you remembered Eq. (3) to be...