Recursion and Recurrence Relations (Home Work)

Question

1. Write down all derangements of the set {α,b,c,d} and show that the number of derangements is the same as predicted by the recurrence D(n) = (n - 1)(D(n - 2) + D(n - 1)) with initial values D(1) = 0 and D(2) = 1.

 

2. Let αk = 3k + k - 2 for all k ≥ 0.

a. Write down the values of α1, α2 and α3.

b. Write down the values of A(1), A(2) and A(3) defined by the recurrence relation: A(0) = -1, A(k) = 3A(k-1) - 2k + 7, k ≥ 1.

c. Show that A(k) = αk is a solution of the recurrence relation for all values of k ≥ 1.


3. Solve the recurrence relation A(n) = 6A(n - 1) - 11A(n - 2) + 6A(n - 3) subject to initial values A(1) = 2, A(2) = 6, A(3) = 20.

Answer 1

1. A derangement is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place.

With 4 elements there are 9 derangements. The derangements of {a, b, c, d} are

{b, a, d, c}, {b, c, d, a}, {b, d, a, c},
{c, a, d, b}, {c, d, a, b}, {c, d, b, a},
{d, a, b, c}, {d, c, a, b}, {d, c, b, a}

From D(n) = (n - 1)(D(n - 2) + D(n - 1)), initial values D(1) = 0, D(2) = 1
D(3) = 2(D(1) + D(2)) = 2(1 + 0) = 2
D(4) = 3(D(3) + D(2)) = 3(2 + 1) = 9

 

2. αk = 3k + k - 2 for all k ≥ 0.

(a) a1 = 31 + 1 -2 = 3 + 1 - 2 = 2
a2 = 32 + 2 - 2 = 9 + 2 - 2 = 9a
a3 = 33 + 3 -2 = 27 +3 -2 = 28

(b) A(0) = -1, A(k) = 3A(k-1) - 2k + 7, k ≥ 1

A(1) = 3A(0) - 2*1 + 7 = -3 -2 + 7 = 2
A(2) = 3A(1) - 2*2 + 7 = 6 - 4 + 7 = 9
A(3) = 3A(2) - 2*3 + 7 = 27 -6 + 7 = 28

(c) It has been shown this is true for k = 1, 2, 3

Suppose it true for k: A(k) = ak = 3k + k - 2

A(k + 1) = 3A(k) - 2k + 7
= 3(3k + k - 2) - 2(k+1) + 7
= 3k+1 + 3k - 6 -2k - 2 + 7
= 3k+! + k - 1
= 3k+1 + (k+1) -2
= ak+1

Shown true by mathematical induction

3. Given A(n) = 6A(n - 1) - 11A(n - 2) + 6A(n - 3).

Assume A(n) = k*rn (k ≠ 0) and substitute these values into the recursive relationship.

k*rn = 6k*rn-1 - 11k*rn-2 + 6k*rn-3
k*rn-3 *(r3 - 6r2 + 11r - 6) = 0

rn-3 ≠ 0, otherwise r = 0 and there would be no value for instance for n = 1.

There is a polynomial and the roots of the equation needs to be found:
r3 - 6r2 + 11r - 6 = 0
(r - 1)(r -2)(r -3) = 0

There are 3 roots, r = 1, r = 2 and r = 3
Then the recursive relationship is A(n) = a*3n + b*2n +c*1n
= a*3n + b*2n +c,
where a, b, c are constants that can be determined from the initial values.

A(1) = 3a + 2b + c = 2
A(2) = 9a + 4b + c = 6
A(3) = 27a + 8b + c = 20

3 A(1): 9a + 6b + 3c= 6
A(2): 9a + 4b + c = 6
Subtracting these two results in 2b + 2c = 0 and c = -b

3 A(2): 27a + 12b + 3c = 18
A(3): 27a + 8b + c = 20
Subtracting these two results in 4b + 2c = -2
With c = -b, 4b + 2c = 4b - 2b = 2b = -2, b = -1
Then c = 1

From A(1) = 3a + 2b + c = 3a -2 + 1 = 2, then a = 1

Then A(n) = 3n - 2n + 1

Answer 2

 

1)  In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

 

Case with 3 letters (A,B,C)

 

Let's select the set (A,B,C) and estimate its permutations:  ABC, BAC, CAB, ACB, CBA, BCA  

 

Only the permutations CAB and BCA can be derangements because all three letters A,B anc C are not located in its original position. The other permutations have at least one letter in its original position.

 

Now, I will use the recursive formulae D(n) to probe that the set (A,B,C) has only 2 derangements.

 

The number of derangements predicted by D(n) = (n - 1)(D(n - 2) + D(n - 1)) when n=3 is:

 

D(3) = (3-1)(D(3-2) + D(3 -1))  =  2(D(1) + D(2))  but D(1)=0 and D(2)=1

 

D(3) = 2( 0 + 1)  = 2        It is correct!!!

 

 

Case with 4 letters (A,B,C,D)

 

Let's select the set (A,B,C,D) and estimate its permutations:

 

ABCD, ABDC, ACBD, ACDB, ADBC, ADCB,

BACD, BADC, BCAD, BCDA, BDAC, BDCA,

CABD, CADB, CBAD, CBDA, CDAB, CDBA,

DABC, DACB, DBAC, DBCA, DCAB, DCBA.

 

Only the permutations:

BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA  are derangements. A total 0f 9 deranggements.

 

Now, I will use the recursive formulae D(n) to probe that the set (A,B,C,D) has only 9 derangements.

The number of derangements predicted by D(n) = (n - 1)(D(n - 2) + D(n - 1)) when n=4 is:

D(4) = (4-1)(D(4-2) + D(4 -1)) = 3(D(2) + D(3)) but D(1)=0 and D(2)=1 and D(3) = 2

 

D(4) = 3( 1 + 2) = 9      It is correct!!!

 

 

2. Let αk = 3k + k - 2 for all k ≥ 0.

 

a. Write down the values of α1, α2 and α3.        a1 = 3(1) + (1) -2  =  2

                                                                     a2 = 3(2) + (2) -2  =  6

                                                                     a3 = 3(3) + (3) -2  = 10

 

b. Write down the values of A(1), A(2) and A(3) defined by the recurrence relation: A(0) = -1, A(k) = 3A(k-1) - 2k + 7, k ≥ 1.

 

A(1)= 3A(1-1) - 2(1) + 7   ⇒  A(1) = 3A(0) -2 +7 = 3(-1) - 2 +7 ⇒     A(1) = 2

 

A(2)= 3A(2-1) - 2(2) + 7 ⇒ A(2) = 3A(1) -4 +7 = 3(2) - 4 +7 ⇒         A(2) = 9

 

A(3)= 3A(3-1) - 2(3) + 7 ⇒ A(3) = 3A(2) -6 +7 = 3(9) - 6 +7 ⇒         A(3) = 28

 

 

c. Show that A(k) = αk is a solution of the recurrence relation for all values of k ≥ 1.

    

    Sorry, but I am not sure which is the meaning that A(k) = ak is a solution. Then, I leave this

    sections (c) and (d) open to be answered by other tutors.