1
$\begingroup$

Is anyone familiar with Einstein's way of summing integers from 1 to n? I am reading the "Heard on The Street" book, which contains Q&A of the interviews for a quant role. And in answers they give the general Gauss methodology of summing integers and then proceed to explain Einstein's way. But the explanation is terrible in my opinion and I cannot wrap my head around it. Would anyone be willing to explain it? (It deals with arrays, they demonstrate the technique on series from 1 to 100)

EDIT: see my answer below for the descriptions of each method.

$\endgroup$
3
  • 1
    $\begingroup$ Are you sure they weren't talking about Einstein's summation notation? $\endgroup$
    – user137731
    Sep 17, 2015 at 13:45
  • 2
    $\begingroup$ Maybe you should include a summary of both the Gauss and the Einstein methodologies, at least for a shorter sum. [I and maybe many others do not have the book you cite.] $\endgroup$
    – coffeemath
    Sep 17, 2015 at 13:46
  • $\begingroup$ Yes, I am sure. $\endgroup$
    – Naz
    Sep 17, 2015 at 13:46

1 Answer 1

1
$\begingroup$

As you are aware, the Gauss method for summing $n$ number of integers is to reverse the series and then add it to itself and divide by two, like so:

If $$S_n = 1 + 2 + 3 + ... + n$$ then we can rewrite that as $$S_n = n+(n-1)+(n-2)+ ... + 1$$ Adding the two together $$2S_n = n(n+1)$$ or $$S_n = \frac{n(n+1)}{2}$$

The crux of the Einstein's method is that it uses triangular numbers. If you imagine each summand as a group of marbles/objects then we can depict them as follows:

enter image description here

But, in our case, the base of the triangle would be 100 marbles long. In fact, the triangle is quadrilateral, so all sides would be 100.

Now, in order to find the number of objects that that triangle is composed of for a given side $n$, we can use a notion of the rectangular numbers. We know that the formula for the number of objects of which the rectangle is composed of is $n(n+1)$. Since, the triangle is composed of half of those, the formula must be $\displaystyle{\frac{n(n+1)}{2}}$. And this is "Einstein's" method of summing a series of integers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .