The Problem
Show that the number of possible links in a computer network of $n$ computers ($n \in Z \land n \geq 1$) is $\frac{n(n-1)}{2}$ in as many ways as you can.
My Work
Solution 1
Given $n$ computers, we can connect them in ${n}\choose{2}$ ways $= \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2} = $ the number of possible connections.
Solution 2
In a $n$ computer network, the first computer $c_1$ will have $n-1$ unique connections with the other $n-1$ computers in the network. The second computer $c_2$ will have $n-2$ unique connections because there are $n-1$ computers, but the connection with $c_1$ has already been counted. By the same logic, $c_3$ will have $n-2$ connections and $c_{n-1}$ will have just $1$ new connection. $c_n$ will have no connections that have not already been counted. The number of connections can therefore be coutned as $1+2+\cdots + n-2 + n-1 = \frac{(n-1)n}{2} = \frac{n(n-1)}{2}$
Solution 3
Base Case
A computer network of $1$ computer has $0$ possible links or $\frac{1(1-1)}{2} = \frac{0}{2} = 0$
Inductive Hypothesis
A computer network of $k$ computers has $\frac{k(k-1)}{2}$ possible links
Induction Step
A network of $k+1$ networks is created by adding $1$ computer to a network of $k$ computers. This computer adds $k$ new possible links to the network, which with the inductive hypothesis, gives us $k+\frac{k(k-1)}{2} = \frac{k(k+1)}{2}$
Solution 4
A computer network can be represented by a graph where the vertex set is the number of computers in the network and the edge set is the number of links in the network. The handshake lemma states $2|E| = \sum{deg(v)}$. If every vertex has a maximum amount of links, each of our $n$ vertices will have a degree of $n-1$, implying $\sum{deg(v)} = 2|E| = n(n-1) \implies |E| = \frac{n(n-1)}{2}$.
Solution 5
A new computer added to a network of $n$ computers will add $n-1$ new links. Thus, the number of links in a $n$ computer network can be described by the recurrence relation $a_n = (n-1) + a_{n-1}$
Let $f(n) = n-1$
$a_1 = (1-1) + 0 = 0 + f(1)$
$a_2 = (2-1) + a_1 = f(2) + f(1)$
$\vdots$
$a_n = f(n) + f(n-1) + \cdots + f(2) + f(1) = \sum{f(k)} = \sum{k-1} = \frac{k(k+1)}{2}-k = \frac{k(k-1)}{2}$
My Question
I'm wondering what other solutions to this question exist. I like to build up a nice repository of solutions for these results, so if you have an additional solution, please share.
Solution 6
There are $n^2$ ordered pairs of computers. In $n$ of these pairs, both members are the same computer. All others come in pairs with reversed order. Thus there are $\frac{n^2-n}2=\frac{n(n-1)}2$ unordered pairs of different computers.
Solution 7
Put the computers in a circle and count the number of connections that a computer has to computers that are clockwise from it, counting $\frac12$ for ties. Then each computer contributes $\frac{n-1}2$ connections, for a total of $n\cdot\frac{n-1}2=\frac{n(n-1)}2$.
Solution 8 (inspired by Gauss)
Number the computers and count the connections twice, first assigning each connection to the computer with the lower number and then assigning each connection to the computer with the higher number. Overall, each computer is assigned $n-1$ connections, and each connection has been counted twice, so there are $\frac{n(n-1)}2$ connections.
Solution 9
Number the computers, label the rows and columns of a grid with the numbers, and mark a connection in each box whose row number is less than its column number. Do this twice, cut out the resulting triangles, turn one of them by $\pi$ and join them into a rectangle of width $n$ and height $n-1$. The rectangle contains $n(n-1)$ boxes, and there are $2$ for each connection, so there are $\frac{n(n-1)}2$ connections.
Solution 10
Number the computers and assign each connection to the computer with the higher number, yielding a count $\sum_{k=1}^n(k-1)$; then use Faulhaber's formula,
$$ \sum_{k=1}^n k^p = {1 \over p+1} \sum_{j=0}^p (-1)^j{p+1 \choose j} B_j n^{p+1-j} $$
to obtain
\begin{align} \sum_{k=1}^n(k-1) &=\sum_{k=1}^{n-1}k^1-\sum_{k=1}^{n-1}k^0\\ &=\frac1{1+1}\sum_{j=0}^1(-1)^j\binom{1+1}jB_jn^{1+1-j}-\frac11\sum_{j=0}^0(-1)^j\binom1jB_jn^{1-j}\\ &=\frac12\left(\binom20B_0n^2-\binom21B_1n\right)-\binom10B_0n\\ &=\frac12\left(n^2+n\right)-n\\ &=\frac{n(n-1)}2\;. \end{align}