1. u should calculate the k variable, that is if i+j=3 (i=1, j=2, or vice versa) then k=3 if i+j=4 (i=1, j=3, or vice versa) then k=2 if i+j=5 (i=2, j=3, or vice versa) then k=1
2. the last question give the answer to the last 2: T(m) = 1 if n = 1 2*T(m - 1) + 1 if n > 1 is the reccurence relation T(m) = 2^m - 1 is the explicit formula. by induction: let's say T(k)=2^k - 1 we need to prove that <<T(k+1)=2^(k+1) -1>> T(k+1)=2*T(k)+1 from the reccurence relation but, we already have T(k) T(k+1)=2*(2^k-1)+1= 2*2^k -2 +1= 2^(k+1) -1 What we needed to prove! We just have to show that its true for k=1: <<by definition>> T(1)=1 <<==>> <<2^k - 1>> 2^1-1=2-1=1 ok? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---