Changes 10/17/14

Java:

• Where the summation identity n(n+1)/2 comes from:
• If you have a sequence 1 + 2 + . . . + n - 1 + n, if you begin with the first and last terms and move inward, you will find that each of these adds to n + 1:
1. 1 + n =  n+1
2. 2 + n-1 = n+1
3. 3 + n-2 = n+1
• So you end up adding (n+1) n / 2 times, because each (n+1) accounts for two elements (one from each end), and therefore there are 1/2 * n instances of (n+1).

• I also tried to understand where the summation identity n(n-1)/2 comes from
• If you have a sequence 1 + 2 + . . . + n - 1, if you begin with the first and last terms and move inward, you will find that each of these adds to n:
1. 1 + n - 1 =  n
2. 2 + n-2 = n
3. 3 + n-3 = n
• But you only have (n-1) of these terms, which is where the n-1 comes from.  Then, like the above identity, you have to divide by 2, so you get a final identity of (n-1)n/2 or n(n-1)/2