5 ms·

> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s

> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s a good place to start learning some of this stuff? By stuff I mean things related to algebra and whatever the black magic I quoted is

jklehm 9y ago
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_mathematical_induction.htm https://www.tutorialspoint.com/discrete_mathematics/discrete...
pkaye 9y ago
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 http://calculus.nipissingu.ca/tutorials/finiteseries.html You can also start your way up from the basics in Khan's Academy.
metahost 9y ago
Any arithmetic book on Sequence and Series will provide you with the basic toolset to derive the above.
feikname 9y ago
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 https://en.wikipedia.org/wiki/Lists_of_mathematics_topics [1] http://www.mathwords.com/ http://www.mathwords.com/ [2] https://brilliant.org/ https://brilliant.org/
toAnswerIt 9y ago
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
- colejohnson66 9y ago
  Random fact: this only works if the series is finite. Otherwise you end up with sum(1...inf) equaling -1/12.
  - skierscott 9y ago
    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.
    - fantispug 9y ago
      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.
  - opportune 9y ago
    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.
  - mywittyname 9y ago
    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 http://mathworld.wolfram.com/RiemannZetaFunction.html
acscott 9y ago
There's a legend, Gauss came up with that while an elementary student: http://www.nctm.org/Publications/Teaching-Children-Mathematics/Blog/The-Story-of-Gauss/ http://www.nctm.org/Publications/Teaching-Children-Mathemati...
- nhebb 9y ago
  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.
  - tomfitz 9y ago
    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
    - nhebb 9y ago
      That's it! Makes me realize how rusty at math I've gotten. :/
  - gordaco 9y ago
    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.
deleted 9y ago
[deleted]
somezero 9y ago
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.
- EpiMath 9y ago
  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.
  - somezero 9y ago
    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.
lowleveldesign 9y ago
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/0465096212 https://www.amazon.com/Magic-Math-Solving-Figuring-Out/dp/04...
fantispug 9y ago
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.
- nileshtrivedi 9y ago
  Author(s)?
  - carlob 9y ago
    Not the same person but I guess he means the one by Graham, Knuth (yeah that one) and Patashnik.
  - thomasahle 9y ago
    Ronald L. Graham, Donald Ervin Knuth, Oren Patashnik
soVeryTired 9y ago
Here are some purely visual proofs of that fact: http://gauravkumar.tech/math/visual-proofs/sum-of-first-n-natural-numbers.html http://gauravkumar.tech/math/visual-proofs/sum-of-first-n-na...
johnsonjo 9y ago
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.

jklehm 9y ago

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_mathematical_induction.htm https://www.tutorialspoint.com/discrete_mathematics/discrete...

pkaye 9y ago

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 http://calculus.nipissingu.ca/tutorials/finiteseries.html You can also start your way up from the basics in Khan's Academy.

metahost 9y ago

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

feikname 9y ago

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 https://en.wikipedia.org/wiki/Lists_of_mathematics_topics [1] http://www.mathwords.com/ http://www.mathwords.com/ [2] https://brilliant.org/ https://brilliant.org/

toAnswerIt 9y ago

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

colejohnson66 9y ago
Random fact: this only works if the series is finite. Otherwise you end up with sum(1...inf) equaling -1/12.
- skierscott 9y ago
  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.
  - fantispug 9y ago
    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.
- opportune 9y ago
  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.
- mywittyname 9y ago
  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 http://mathworld.wolfram.com/RiemannZetaFunction.html

acscott 9y ago

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

nhebb 9y ago
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.
- tomfitz 9y ago
  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
  - nhebb 9y ago
    That's it! Makes me realize how rusty at math I've gotten. :/
- gordaco 9y ago
  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.

deleted 9y ago

[deleted]

somezero 9y ago

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.

EpiMath 9y ago
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.
- somezero 9y ago
  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.

lowleveldesign 9y ago

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/0465096212 https://www.amazon.com/Magic-Math-Solving-Figuring-Out/dp/04...

fantispug 9y ago

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.

nileshtrivedi 9y ago
Author(s)?
- carlob 9y ago
  Not the same person but I guess he means the one by Graham, Knuth (yeah that one) and Patashnik.
- thomasahle 9y ago
  Ronald L. Graham, Donald Ervin Knuth, Oren Patashnik

soVeryTired 9y ago

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

johnsonjo 9y ago

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.