Prove that the sum of numbers written on the board is always equal to $\binom{20}{2}$ We write the number $20$ as the sum of two numbers $a,b$ and write $ab$ on the board where $a,b \ge 1$. We do this again for $a,b$ until we get only (multiple instances of) the number $1$. Prove that the sum of numbers written on the board is always equal to $\binom{20}{2}$.
I don't know how should I work to get a combination; it is more likely to get a sum?
 A: To elaborate on the hint I left in the comments:
Consider a complete graph on $20$ vertices. We know that the graph has $20 \choose 2$ edges; we will count the edges a different way. Separate the graph into two disjoint subgraphs $A,B$ of order $a$ and $b$ (so $a+b=20$). There are $ab$ edges in total between $A$ and $B$. Now continue the process on $A$ and $B$. In the end, we will have counted every edge once, so the sum of the products $ab$ must be $20 \choose 2$.
A: Generalise and prove by induction. For any node labelled $n$ the sum of products over its subtree should be $\binom n2$. This is true for leaf nodes (the sum being empty and $\binom12=0$), and assuming it for children labelled $a,b$, the total sum becomes $\binom a2+\binom b2+ab$. It is not hard to show this is $\binom{a+b}2$. In fact the set of pairs that can be formed from $a$ white balls and $b$ black balls contains $\binom a2$ white pairs, $\binom b2$ black pairs, and $ab$ mixed colour pairs. Or attach triangles of $\binom a2$ and $\binom b2$ points respectively to two sides of a $a\times b$ rectangular array of points, to get a triangular array with $a+b$ points along any side; this for those more visually oriented.
A: This process can be described as follows:
$F(n) = a \cdot (n-a) + F(a) + F(n-a)$ where $F(0) = F(1) = 0$.
(In other words, given some $n$, we're choosing a value for $a$ and letting $b=n-a$, so that $a+b=n$)
Try with $a=1$:
$F(n) = 1 \cdot (n - 1) + F(1) + F(n-1) = n - 1 + F(n-1) = \sum_{k=1}^{n} (k-1) = \frac{n(n-1)}{2}$
This at least gives us an easy way to compute $F(n)$ assuming we always choose $a=1$. 
Let's try again using induction, with the hypothesis that $F(n) = \frac{n(n-1)}{2}$ is true regardless of $a$ by substituting:
$F(n) = a \cdot (n-a) + \frac{a(a-1)}{2} + \frac{(n-a)(n-a-1)}{2} = \frac{n(n-1)}{2}$
All the $a$-terms cancel out, so $F(n)$ does not depend on $a$. It will always be equal to $\frac{n(n-1)}{2} = \binom{n}{2}$ 
A: This is actually quite a lovely problem. 
Intuitively, the problem initially seems quite tricky, or, at least, it did to me. 
Starting with the natural number $n$ we split it into two others $a+b$, then take the product $ab$ and iterate this process of spitting $a$ and $b$ multiplying etc. Eventually summing all pairs of products.
In order to gain some intuition for this process I figured that we need some way of coping with both $a+b$ and $ab$ together. The simplest way to do this is to square $n$:
$$n^2=(a+b)^2=a^2+2ab+b^2$$
We have the sum $a+b$ on the left (albeit squared) and the product $ab$ on the right. 
Then, iterating this process: Each of $a$ and $b$ can be written as sums of natural numbers themselves, say $a=c+d$ and $b=e+f$, then expanding
$$n^2=c^2+d^2 + e^2 + f^2 + 2(cd+ab+ef)$$
and so on until we reach 
$$n^2=\underbrace{1^2+1^2+\cdots +1^2}_{\text{$n$ times}} + 2S$$
where $S$ is the desired sum of all products.
It should be clear that there will always be $n$ $1^2$ terms: 

To picture this imagine $n^2$ as the area of a square of side $n$. At each iteration we split along the horizontal and vertical of smaller and smaller squares that lie along the diagonal. Eventually we are left with the $n$ leading diagonal $1\times 1$ squares, each of area $1^2$.

So
$$n^2=n+2S$$
therefore
$$S=\frac{n(n-1)}{2}=\binom{n}{2}$$
