Finding a recursive formula for a number

Question

I am trying to find a recursive formula for a given number in order to solve a problem I am working on.

For every $n \in \mathbb{N} \setminus \lbrace 0,1 \rbrace$ we define the number \begin{align}S(n)= &1\times2 + 1 \times 3 + \dots + 1 \times n \\&+ 2 \times 3 + 2 \times 4 + \dots + 2 \times n \\ &+ \dots \\ &+ (n-2)\times (n-1) + (n-2) \times n \\ & +(n-1) \times n \end{align}

My idea was to compute $S(n+1)$ and then subtract it from the above definition, but no matter how hard I try, nothing remotely right comes out: \begin{align}S(n+1)=& 1 \times 2 + 1 \times 3 + \dots + 1 \times n + 1 \\ & +2 \times 3 + 2 \times 4 + \dots + 2 \times n + 2 \\& + \dots \\ & + (n-1) \times n + (n-1) \times(n+1) \\ & + n \times (n+1) \end{align}

I see that at the end of every lin of $S(n+1)$ there seems to emerge the sum of the natural numbers. Subtracting $S(n)$ from the above most terms should cancel, however what I come out with is nothing useful. Am I doing something absolutely wrong?

Answer 1

It's easiest to just write out $S(n+1)$ as you did and notice that in each row, the only difference is that $S(n+1)$ has an extra $1(n+1), 2(n+1),\cdots,(n-1)(n+1),n(n+1)$ in the right column. It quickly follows that:

$$S(n+1)-S(n)=(n+1)\sum_{i=1}^n i = (n+1)\frac{n(n+1)}{2},$$

For example, $S(2)=1\times2=2$ and $S(3)=1\times2+1\times3+2\times3=11$, and $S(3)-S(2)=9=3\cdot \frac{2\cdot 3}{2}$.

For what it's worth you can derive an explicit formula for $S(n)$ by summing over $n$:

$$S(n)-S(2)=\sum_{k=2}^{n-1}(n+1)\frac{n(n+1)}{2}=\frac{1}{24}(n-2)(24+13n+8n^2+3n^3),$$

which was calculated by expanding the products and using summations for $\sum n$ and $\sum n^2$. Testing this for $n=3$ gives:

$$S(3)-S(2)=9$$

as expected.

Answer 2

$$S(n) = \sum_{i=1}^{n-1} \sum_{j=i+1}^nij$$ $$S(n+1) = \sum_{i=1}^{n} \sum_{j=i+1}^{n+1}ij = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n+1}ij + n(n+1) =$$ $$= \sum_{i=1}^{n-1}\left(\sum_{j=i+1}^{n}ij + i(n+1)\right) + n(n+1) =$$ $$= \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}ij + \sum_{i=1}^{n-1}i(n+1) + n(n+1) =$$ $$= S(n) + (n+1)\frac{(n-1)n}{2}+ n(n+1) =$$ $$= S(n) + n(n+1)\left(\frac{n-1}{2}+ 1\right) =$$ $$= S(n) + \frac{n(n+1)^2}{2}.$$

For example:

$$S(2) = 2$$ $$S(3) = 1\cdot 2 + 1 \cdot 3 + 2 \cdot 3 = 2 + 3 + 6 = 11$$ $$S(3) = S(2) + \frac{2(2+1)^2}{2} = 2 + 9 = 11$$

Answer 3

It's possible to derive an explicit formula for your sum as well.

Your sum contains the product $i \times j$ for every pair with $1 \le i < j \le n$. We could double your sum by, for every term $i \times j$ in it, adding the term $j \times i$. So you get

$$2 S(n) = \sum_{1 \le i \le n} \sum_{1 \le j \le n, j \not = i} i \times j$$

The sum on the right looks a bit tricky, but we could add in the terms with $i = j$. Those are just $1^2, 2^2, \ldots, n^2$, and so we have

$$2 S(n) + (1^2 + 2^2 + \cdots + n^2) = \sum_{1 \le i \le n} \sum_{1 \le j \le n} i \times j$$.

The double sum factors, and you get

$2 S(n) + (1^2 + 2^2 + \cdots + n^2) = \left( \sum_{1 \le i \le n} i \right) (\sum_{1 \le j \le n} j)$.

If you recall $1 + 2 + \cdots + n = n(n+1)/2, 1^2 + 2^2 + \cdots + n^2 = n(n+1)(2n+1)/6$ then you get

$$2 S(n) + {n(n+1)(2n+1) \over 6} = \left( {n(n+1) \over 2} \right)^2$$

which you can solve for $S(n)$:

$$2 S(n) = {n(n+1) \over 2} \left( {n(n+1) \over 2} - {2n+1 \over 3} \right)$$

$$2 S(n) = {n(n+1) \over 2} \left( {3n(n+1) - 2(2n+1) \over 6} \right)$$

$$2 S(n) = {n(n+1) \over 2} \left( {3n^2 - n - 2 \over 6} \right)$$

$$ S(n) = {n(n+1)(3n^2-n-2) \over 24} $$