3i won't be using double summation again and again.
let S = what we need to find out.
now, since i = 0,1,2 .... ,(n-1).
and j = 1,2,.....,n.
w may write (n-i) = n , ...., 2, 1 = j.
and similalrly (n-j) as i.
since i < j.
n-j > n-i.
hence n-i and j are in one - one correspondance.
similarly n-j and i are in one - one correspondance.
ds = double summation.
S = ds ( n-jC(n,n-j) + n-iC(n,n-i))
S = ds ( nC(n,i) + nc(n,j)) - S
or, 2S = n*ds(1C(n,i) + 1C(n,j))
S = n2*ds(1C(n,i) + 1C(n,j))
S = n2*[Σn-rC(n,r) + ΣrC(n,r)]
in the first summation in the square bracket we put the lower limit as r = 0 and the upper limit as r = n-1.
in the second one we put the lower limit as = 1 and the upper limit as r = n.
so we have simply
S = n2ΣnC(n,r).
which was what we wanted.
this one - one correspondance thing helps in solving almost all of these type of problems...
