Answer:
A) [tex]a_{1}[/tex] = 1, [tex]a_{2}[/tex] = 4
B) [tex]a_{n}[/tex] = 2[tex]a_{n-1}[/tex] + 2
C) [tex]a_{n} = 2^{n-1} + 2^n -2\\a_{n} = 2^n + 2^{n-1} -2[/tex]
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)
[tex]a_{1}[/tex] = no of comparisons in set (s)
that contains 2 elements = 1
[tex]a_{2}[/tex] = no of comparisons in set (s) containing 4 = 4
B) an = 2a[tex]_{n-1}[/tex] + 2
C) using the recurrence relation
a[tex]_{n}[/tex] = 2a[tex]_{n-1}[/tex] + 2
substitute the following values 2,3,4 .......... for n
a[tex]_{2}[/tex] = 2a[tex]_{1}[/tex] + 2
a[tex]_{3}[/tex] = 2a[tex]_{2}[/tex] + 2 = [tex]2^{2} a_{1} + 2^{2} + 2[/tex]
a[tex]_{4}[/tex] = [tex]2a_{3} + 2 = 2(2^{2}a + 2^{2} + 2 ) + 2[/tex]
= [tex]2^{n-1} a_{1} + \frac{2(2^{n-1}-1) }{2-1}[/tex] ---------------- (x)
since 2^1 + 2^2 + 2^3 + ...... + 2^n-1 = [tex]\frac{2(2^{n-1 }-1) }{2-1}[/tex]
applying the sum formula for G.P
[tex]\frac{a(r^n -1)}{r-1}[/tex]
Note ; a = 2, r =2 , n = n-1
a1 = 1
so equation x becomes
[tex]a_{n} = 2^{n-1} + 2^n - 2\\a_{n} = 2^n + 2^{n-1} - 2[/tex]
