Question

For n ≥ 1, let S be a set containing 2n distinct real numbers. By an, we denote the number of comparisons that need to be made between pairs of elements in S in order to determine the maximum and minimum elements in S.

Requried:
a. Find a1 and a2
b. Find a recurrence relation for an.
c. Solve the recurrence in (b) to find a formula for an.

Answer 1

A)
`a_(1)` = 1,
`a_(2)` = 4

B)
`a_(n)` = 2
`a_(n-1)` + 2

C)
`a_(n) = 2^(n-1) + 2^n -2\\a_(n) = 2^n + 2^(n-1) -2`

Explanation:

For n ≥ 1 ,

S is a set containing 2^n distinct real numbers

an = no of comparisons to be made between pairs of elements of s

A)

`a_(1)` = no of comparisons in set (s)

that contains 2 elements = 1

`a_(2)` = no of comparisons in set (s) containing 4 = 4

B) an = 2a
`_(n-1)` + 2

C) using the recurrence relation

a
`_(n)` = 2a
`_(n-1)` + 2

substitute the following values 2,3,4 .......... for n

a
`_(2)` = 2a
`_(1)` + 2

a
`_(3)` = 2a
`_(2)` + 2 =
`2^(2) a_(1) + 2^(2) + 2`

a
`_(4)` =
`2a_(3) + 2 = 2(2^(2)a + 2^(2) + 2 ) + 2`

=
`2^(n-1) a_(1) + (2(2^(n-1)-1) )/(2-1)` ---------------- (x)

since 2^1 + 2^2 + 2^3 + ...... + 2^n-1 =
`(2(2^(n-1 )-1) )/(2-1)`

applying the sum formula for G.P

`(a(r^n -1))/(r-1)`

Note ; a = 2, r =2 , n = n-1

a1 = 1

so equation x becomes

`a_(n) = 2^(n-1) + 2^n - 2\\a_(n) = 2^n + 2^(n-1) - 2`