Conjecture to start a proof

Question

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.

Answer 1

Hint: You have to use the identity $$ \sum_{i=1}^nn^2=\frac{n(n+1)(2n+1)}{6}. $$

Answer 2

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.

Answer 3

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.