55
Explanation:
Sum(from K = 1 to N) of K = Total(N) = T(N)
T(N) = 1 + 2 + 3 + … + N
Subtract one from each of N terms.
T(N) = N + (0 + 1 + 2 + … + (N - 1))
T(N) = N + T(N - 1)
Explicitly writing out T(N - 1) in the previous form. This is the same as 1 + 2 + … + 9.
T(N) = N + (1 + 2 + 3 + … + (N - 1))
Subtract one from each of N - 1 terms.
T(N) = N + (N - 1) + (0 + 1 + 2 + … + (N - 2))
T(N) = N + (N - 1) + T(N - 2)
Subtract one from each of N - 2 terms.
T(N) = N + (N - 1) + (N - 2) + T(N - 3)
T(N) = N + (N - 1) + (N - 2) + … + (N - N)
Rewriting without parenthesis.
T(N) = N + N - 1 + N - 2 + … + N - N
Now rearrange the terms so it's all N's at the beginning and all other numbers after.
T(N) = N * N - (1 + 2 + ... + (N - 1))
To give a concrete example with T(4):
T(4) = 4 + (4 - 1) + (4 - 2) + (4 - 3) + (4 - 4)
T(4) = 4 + 4 - 1 + 4 - 2 + 4 - 3 + 4 - 4
T(4) = 4 + 4 + 4 + 4 + 4 - 4 - 1 - 2 - 3
Cancelling out the - 4 with a + 4.
T(4) = 4 + 4 + 4 + 4 - 1 - 2 - 3
T(4) = (4 + 4 + 4 + 4) - (1 + 2 + 3)
Divide the left term by four.
T(4) = 4 * (1 + 1 + 1 + 1) - (1 + 2 + 3)
T(4) = 4 * (4) - (1 + 2 + 3)
Another concrete example with T(5):
T(5) = 5 + (5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) + (5 - 5)
T(5) = 5 + 5 - 1 + 5 - 2 + 5 - 3 + 5 - 4 + 5 - 5
T(5) = 5 + 5 + 5 + 5 + 5 + 5 - 5 - 1 - 2 - 3 - 4
Cancelling out the -5 with a + 5.
T(5) = 5 + 5 + 5 + 5 + 5 - 1 - 2 - 3 - 4
T(5) = (5 + 5 + 5 + 5 + 5) - (1 + 2 + 3 + 4)
Divide the left term by five.
T(5) = 5 * (1 + 1 + 1 + 1 + 1) - (1 + 2 + 3 + 4)
T(5) = 5 * (5) - (1 + 2 + 3 + 4)
Back to our original example:
T(N) = N * N - (1 + 2 + ... + (N - 1))
T(N) = N * N - (T(N - 1))
This next bit is very important. We already know from above that T(N) = N + T(N - 1). So we're going to subtract N to from sides of the equation.
T(N) - N = N * N - T(N - 1) - N
Adding parenthesis for clarity. Note that when we bring the - N at the end inside the parenthesis the sign changes.
T(N) - N = N * N - (T(N - 1) + N)
Reordering the last term for clarity.
T(N) - N = N * N - (N + T(N - 1))
Then we replace (N + T(N - 1)) with T(N).
T(N) - N = N * N - (T(N))
Removing parenthesis for clarity.
T(N) - N = N * N - T(N)
Add T(N) to both sides of the equation.
T(N) - N + T(N) = N * N - T(N) + T(N)
Reorder the left side and cancel the T(N) terms on the right side.
T(N) + T(N) - N = N * N
2 * T(N) - N = N * N
Add N to both sides.
2 * T(N) = N * N + N
Divide both sides by two.
T(N) = (N * N + N) / 2
A couple ways to rewrite the same thing.
T(N) = (N^2 + N) / 2
T(N) = (N * (N + 1)) / 2
So for your original question:
T(10) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
We know that T(N) = (N^2 + N) / 2
T(10) = (10^2 + 10) / 2
T(10) = (100 + 10) / 2
T(10) = (110) / 2
T(10) = 55
