Conjecture to start a proof In an inductive proof example, my book starts with the identity stating $$\sum\limits_{i=1}^n \sum\limits_{j=1}^i j = \frac{n(n+1)(n+2)}{6}\;.$$ As a sidenote, it says they reached this identity by conjecture, calculating the double sum for low values of $n$. How on earth did they see this? 
I attempted this expansion (don't know if it's right): $$\sum\limits_{i=1}^n \sum\limits_{j=1}^i j = \sum\limits_{i=1}^n (1 + 2 +\ldots+i) = 1 + 2 + \ldots + \sum\limits_{i=1}^n i = 1 + 2 + \ldots + (1 + 2 + \ldots + n)\;.$$
From this, I don't see how they arrived at the fractional cubic polynomial. Any help would be appreciated! Thanks.  
 A: The first few values of $$s_n=\sum_{i=1}^n\sum_{j=1}^ij$$ are:
$$\begin{array}{rcc}
n:&1&2&3&4&5\\
s_n:&1&4&10&20&35
\end{array}$$
Anyone familiar with binomial coefficients will recognize that bottom row as the numbers $\binom{k}3$ for $k=3,4,5,6,7$, and
$$\binom{k}3=\frac{k!}{3!(k-3)!}=\frac{k(k-1)(k-2)}6\;.$$
Thus, $$s_n=\binom{n+2}3=\frac{(n+2)(n+1)n}6=\frac{n(n+1)(n+2)}6\;.$$
In other words, it’s a very natural guess if you have the right background, but I agree that it’s not at obvious if you don’t have that background.
Your expansion, however, is not correct:
$$\sum_{j=1}^ij=1+2+\ldots+i=\frac{i(i+1)}2\;,$$
so
$$s_n=\sum_{i=1}^n\frac{i(i+1)}2=\frac12\sum_{i=1}^n\left(i^2+i\right)=\frac12\sum_{i=1}^ni^2+\frac12\sum_{i=1}^ni=\frac12\sum_{i=1}^ni^2+\frac14n(n+1)\;.$$
To finish the job by this route, you need to know that
$$\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}6$$
and simplify
$$\frac{n(n+1)(2n+1)}{12}+\frac14n(n+1)$$
to get the desired expression. Of course you can also simply prove by induction on $n$ that 
$$s_n=\frac{n(n+1)(n+2)}6\;,$$
once you’ve guessed the formula.
A: Spoiler alert: I explain the hint given by Boris below.
Maybe try this:
$\sum_{i=1}^n\sum_{j=1}^i j = \sum_{i=1}^n\left(\frac{i(i+1)}{2}\right) = \frac{1}{2}\sum_{i=1}^n i^2+i = \frac{1}{2}\sum_{i=1}^n i^2 + \frac{1}{2}\sum_{i=1}^n i = \frac{1}{2}\frac{n(n+1)(2n+1)}{6}+\frac{1}{2}\frac{n(n+1)}{2}$
These just rely on well-known formulas for the sum of integers and squares, if you're allowed to use those.
A: By analogy with integration, it's reasonable to hypothesise that a double-sum of linear terms will be a cubic. (With the right tools, this can be formulated precisely and proved). Following that hypothesis, it is a simple matter to calculate the first 4 terms and derive the unique cubic which fits them.
A: Hint: You have to use the identity
$$
\sum_{i=1}^nn^2=\frac{n(n+1)(2n+1)}{6}.
$$
