Advertisement
andrelaszlo

stackoverflow proof sketch

Feb 19th, 2015
231
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. Let C = 99^2 and A = {a_i,j where 0<i<99, 0<j<99} and assume that each element
  2. in A is labeled A_n where 0<n<C. The same goes for b and B.
  3.  
  4. The sum that you are asking for, let's call it S, can be written as
  5.  
  6. S = (A_0 - B_0) + (A_0 - B_1) + ... + (A_0 - B_C) +
  7. (A_1 - B_0) + ... + (A_1 - B_C) +
  8. ...
  9. (A_C - B_0) + ... + (A_C - B_C)
  10.  
  11. A_0 occurs C times in the first row and the B terms can be written
  12. as -(B_0 + B_1 + ... + B_C), i.e.:
  13.  
  14. C*A_0 - (B_0 + B_1 + ... + B_C)
  15.  
  16. The sum B_0 + B_1 + ... + B_C is of course the sum of all elements in B. Let's
  17. call this S_B, and the sum of all elements in A S_A. The first row can be
  18. written as:
  19.  
  20. C*A_0 - S_B
  21.  
  22. The second row has exactly the same B terms but has A_1 instead of A_0, so:
  23.  
  24. C*A_1 - S_B
  25.  
  26. Now we can write S like:
  27.  
  28. S = C*A_0 - S_B +
  29. C*A_1 - S_B +
  30. ...
  31. C*A_C - S_B
  32.  
  33. The sum of the A terms in S can be written as C*(A_0 + A_1 + ... + A_C) and S_B
  34. occurs C times as well, so we end up with:
  35.  
  36. S = C*S_A - C*S_B
  37. = C(S_A - S_B)
  38. = 99^2 * ((A_0 + A_1 + ... + A_C) - (B_0 + B_1 + ... + B_C))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement