Homework 16

Questions 9.3 from the course text.

Solution

Average number of tracks 
= (Sum_{j=1}^n Sum_{i=1}^n |j-i|) / (Sum_{j=1}^n Sum_{i=1}^n 1)
= 2/(n^2) [ Sum_{j=1}^n Sum_{i=1}^j (j-i) ]
= 2/(n^2) [ Sum_{j=1}^n (j^2 - j(j+1)/2 ]
= 2/(n^2) [ Sum_{j=1}^n ( (j^2)/2 - j/2 ) ]
= 1/(n^2) [ Sum_{j=1}^n (j^2 - j) ]
= 1/(n^2) [ (2n^3 + 3n^2 + n)/6 - n(n+1)/2 ]
= 1/(n^2) [ (2n^3 + 3n^2 + n)/6 - (3n^2 + 3n)/6 ]
= 1/(n^2) [ (2n^3 - 2n)/6 ]
= (n^3 - n) / 3(n^2)
= n/3 - 1/(3n)
--> n/3 as n gets large