This would be a finite series. I think it is usually covered in calculus courses but some of the basics are discussed in earlier algebra courses. Here is a link to a brief summary on finite series. http://calculus.nipissingu.ca/tutorials/finiteseries.html

You can also start your way up from the basics in Khan's Academy.

There's a legend, Gauss came up with that while an elementary student: http://www.nctm.org/Publications/Teaching-Children-Mathemati...

I came up with it too when I was in school. I was bored and staring at some tiles and noticed that for a square block of tiles with side = n, n^2 = sum(1...n) - sum(1...n-1).

The funny thing is that, since then, I've looked at that formula several times and can't for the life of me figure out I got from the above formula to the the sum of the range formula. I guess younger me was smarter than current me.

You can arrive to the formula n^2 = sum(1..n) + sum(1..n-1) visually, separating a square into two triangles and fill them adding diagonals. Ok, that doesn't sound very informative, so let me show you an example.

Let's start with a 4x4 square:

OOOO

OOOO

OOOO

OOOO

Divide it into two triangles:

OOOO

OOO O

OO OO

O OOO

Note that one of the triangles has a side of (n-1) and other has a side of n. Now, let's see how many elements has each triangle. As I said, we can use diagonal lines. So the first diagonal has 1 element:

O

We then add the second diagonal, which has 2 elements (I'll use lower caps for the elements that were already present):

oO

O

The third one has 3 elements:

ooO

oO

O

And finally we add the last one:

oooO

ooO

oO

O

It's easy to see how this procedure can be extended to any triangle and to any square (which can be divided in two triangles).

So we can see that:

1) A triangle of side n has sum(1..n) elements.

2) A square of side n can be decomposed into a triangle of side n and another one of side (n-1).

3) Now you can use some basic algebra to determine the value of sum(n): if sum(n-1) + sum(n) = n^2, and sum(n-1) + n = sum(n), then 2·sum(n) = n^2+n, therefore sum(n) = (n^2+n)/2, or if you prefer, sum(n)=n·(n+1)/2.

That is an outstanding explanation of the intuition behind that formula, and in ASCII no less! :)

That's a neat visualisation.

n^2 = sum(1..n) - sum(1..n-1) = 2sum(1..n-1) + n

=> n^2 - n = 2sum(1..n-1) => n(n-1) = 2*sum(1..n-1) => sum(1..n-1) = n(n-1)/2

And you can rewrite that as... sum(1..n) = n(n+1)/2

That's it! Makes me realize how rusty at math I've gotten. :/

Isn't sum(1...n) - sum(1...n-1) just n? (1+2+3+4+5 - (1+2+3+4) = 5). That should be a +, right?

This is an awesome visualization, by the way.

> Isn't sum(1...n) - sum(1...n-1) just n?

Yes. I meant n^2 = sum(1..n-1) + sum(1..n).

You may have a look at “The Magic of Math” [1]. I’m reading it right now and I am loving it. It contains a lot of interesting problems from arithmetics, algebra and geometry. They are well explained and show that math is about creative thinking and not about memorizing equations.

[1] https://www.amazon.com/Magic-Math-Solving-Figuring-Out/dp/04...

Honestly math is filled with cool stuff like this. In fact sometimes I wish I would have done a math minor or major at University instead of just a Computer Science major and Information Systems minor (I’m finishing my undergrad in the spring.)

Combinatorics is one of my favorite fields I always feel it has a lot of cool gems like that one and the proofs are often really intuitive. Combinatorics is all about counting things like the number of possible poker hands given a single deck or the number of ways you can seat 4 people around a table.

It was already mentioned below but, discrete math is another good one. Discrete math includes combinatorics, graph theory, set theory, logic, and number theory. All of these have really cool little tidbits of information. My Discrete Math course was my favorite class at university so far. One of the first random bits of information I learned in that class was that any number is divisible by 9 if the sum of it’s digits are divisible by 9 this was posed to us in one of our first homeworks to be proven or disproven and we were able to prove it using some algebra.

I really like the book “Concrete Mathematics”. It might be a little hard going without much maths background, but it is filled with these kinds of tricks.

Author(s)?

Not the same person but I guess he means the one by Graham, Knuth (yeah that one) and Patashnik.

Ronald L. Graham, Donald Ervin Knuth, Oren Patashnik

Discrete mathematics is the branch of math you're after.

This looks like it has some ok examples: https://www.tutorialspoint.com/discrete_mathematics/discrete...

to see it consider this:

S = 1 + 2 + 3 + ... + n-1 + n

+

S = n + n-1 + n-2 + ...+ 2 + 1

=

2S = n+1 + n+1 + n+1 + ... + n+1 + n+1

every column sums to n+1

I always understood it just by saying "Okay, if we take the last item and the first (so n+1), and then the second to last item and second item (so n-1 + 2 = n + 1), etc, we get to the middle in n/2 times. If it was odd, we have an extra n/2. But trying it out on a few series, and it's obvious it works out each way, odd or even, to n/2 * (n + 1).

Random fact: this only works if the series is finite. Otherwise you end up with sum(1...inf) equaling -1/12.

That's the sum of all integers on the complex plane, solved using an analytical continuation of the Riemann zeta function at -1 (fwiw, by the same definition, the sum of 13, 26, 39...inf is also -1/12).

It's disingenuous to assert that is same as the sum of that infinite series without the associated caveats. By the definitions of infinite series that we all learned in calculus, that is a divergent series with no sum.

Edit: Wolfram Alpha[0] has a good graphic showing why this series converges to -1/12 (the one with the red line, drawing a peach-like shape). It also gives an intuition as to how complex numbers are influencing the results despite being omitted from the equation.

[0] http://mathworld.wolfram.com/RiemannZetaFunction.html

Not true. Infinite sums are not defined for series that don’t converge, and sum(1..n) does not converge as n => infinity.

Yes, you can play a nice trick with that sum if you ignore the fact that inf-inf is meaningless.

It depends on how you define the summation of infinite series. With the standard convergence type definitions you are correct. But it is possible to define this sum in a consistent way (e.g. Ramanujan summation or Riemann Zeta analytic continuation) as shown in Hardy's “Divergent Series”. The cost is that they have properties like rearranging the order of the terms gives a different result. Apparently this sum can come up in Quantum Field Theory when calculating vacuum force between two conducting plates.

This can be disproven by noting that the naturals are closed under addition.

The math involved in reaching this identity is akin to dividing by zero.

I do not have an formal math education, but I'm fairly sure what you quote is part of the Arithmetic Progression concept (the sum formula more specifically), so taking a look at the arithmetic branch of math might be a good idea.

Wikipedia[0], MathWords[1] and Brilliant[2] might be some good resources for you.

[0] https://en.wikipedia.org/wiki/Lists_of_mathematics_topics [1] http://www.mathwords.com/ [2] https://brilliant.org/

Here are some purely visual proofs of that fact: http://gauravkumar.tech/math/visual-proofs/sum-of-first-n-na...

Read G.H. Hardy's Introduction to Number Theory, Then possibly A Course of Pure Mathematics, also by him.

Note that the level for which you're aiming, is a level wherein such summation is much closer to triviality, than it is to `black magic` - whatever that means.

If you mean Hardy and Wright's Introduction to the Theory of Numbers, I agree it is excellent, but you can solve the great majority of the project Euler problems without going to quite that level. I particularly enjoyed Daniel Shank's Solved and Unsolved Problems in Number Theory but even that goes beyond what is necessary.

I'll check Daniel Shanks' book out. But the OP was interested in reaching a level where the proof of such summation is not `black magic` - at least that was my impression - which implies reaching a level considerably higher than the minimum... Hardy would be helpful, and is at a sufficiently higher level than future Project Euler questions he might encounter e.g. those involving continued fractions, or Diophantine equations, or even modular arithmetic etc.

Any arithmetic book on Sequence and Series will provide you with the basic toolset to derive the above.