I also like the more visual geometric proof of this formula. Say you want the sum of 1-4, you can make this shape:
*
**
***
****
The area of this triangle is then equivalent to our original problem, the sum of the first 4 natural numbers. But, it's hard to find the area of this "triangle", but easy if you make a rectangle (#s are a second, rotated copy of the triangle)
*####
**###
***##
****#
This is a 5x4 rectangle, so its area is 20. The rectangle is made of two of the triangles we want to know the area of, so the sum is 20/2 = 10.
If you generalize this to the first n natural numbers, you do indeed get the formula n (n + 1) / 2
This is great! I sketched something similar in this post on quadratic complexity jarednielsen.com/big-o-quadratic-t..., but I like yours better. Do you mind if I use it? With credit, of course.
I also like the more visual geometric proof of this formula. Say you want the sum of 1-4, you can make this shape:
The area of this triangle is then equivalent to our original problem, the sum of the first 4 natural numbers. But, it's hard to find the area of this "triangle", but easy if you make a rectangle (#s are a second, rotated copy of the triangle)
This is a 5x4 rectangle, so its area is 20. The rectangle is made of two of the triangles we want to know the area of, so the sum is 20/2 = 10.
If you generalize this to the first n natural numbers, you do indeed get the formula
n (n + 1) / 2There is no excuse to forget the formula now!
I mean, you don't even need to list cases.
This is great! I sketched something similar in this post on quadratic complexity jarednielsen.com/big-o-quadratic-t..., but I like yours better. Do you mind if I use it? With credit, of course.
Sure, go ahead!