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

Answer:

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$

Step-by-step 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} + \frac{2(2^{n-1}-1) }{2-1}$   ---------------- (x)

since  2^1 + 2^2 + 2^3 + ...... + 2^n-1 =  $\frac{2(2^{n-1 }-1) }{2-1}$

applying the sum formula for G.P

$\frac{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$