closed form for $d(4)=2$, $d(n+1)=d(n)+n-1$? I am helping a friend in his last year of high school with his math class. They are studying recurrences and proof by inference. One of the exercises was simply "How many diagonals does a regular $n$-polygon have?".
We quickly found a direct answer to that question: $d(n) = \frac{(n-3)n}2$, but since they are studying recurrences, we didn't stop, and found the recurrence $d(n+1)=d(n)+n-1$. We proceeded to prove by induction that the closed form we initially found is indeed a solution for the recurrence.
But then he asked me a question I couldn't answer: we found the closed form because the question gives us an obvious mapping to an easy to solve geometry problem, but is there a way to find a closed form using the recurrence only?
 A: You can think of your recurrence as a difference equation, stating that
$$ d(n+1)-d(n)=n-1, $$
with some initial condition. At some point (18th century, say), people knew a lot about difference sequences. In particular, if the difference sequence is a polynomial of degree $k$, then the original one is a polynomial of degree $k+1$ (and vice versa). There is even a formula that will give you the coefficients, but if you're lazy you can simply write (in this case)
$$ d(n) = An^2 + Bn + C, $$
substitute some small $n$, and solve for $A,B,C$.
A: As has been pointed out, $d(n+1)-d(n)=n-1$, or equivalently, $d(n)-d(n-1)=n-2$. The inverse of the finite difference operator is summation, just like the inverse of the derivative is integration. To be precise:
$$
\begin{align}
d(n)&=d(4)+\sum_{k=5}^n\;(d(k)-d(k-1))\\
&=2+\sum_{k=5}^n\;(k-2)\tag{1}
\end{align}
$$
There are many approaches to computing the summation in $(1)$. One of the simplest, commonly attributed to Gauss as a child, is:
$$
\begin{array}{lc@{+}c@{+}c@{+}c@{+}c}
\text{sum forward}&3&4&5&\dots&(n-2)\\
\text{sum backward}&(n-2)&(n-3)&(n-4)&\dots&3\\
\text{sum of sums}&(n+1)&(n+1)&(n+1)&\dots&(n+1)
\end{array}
$$
there are $n-4$ colums, so twice the sum is $(n-4)(n+1)$. Therefore,
$$
\begin{align}
d(n)&=2+\frac{(n-4)(n+1)}{2}\\
&=\frac{n^2-3n}{2}
\end{align}
$$
A: 
we found the closed form because the question gives us an obvious mapping to an easy to solve geometry problem, but is there a way to find a closed form using the recurrence only?

In general there is no closed form, similar to the lack of a closed form for integrals of functions in calculus.  If there recurrence had been $d(n+1)-d(n)=2^{n^2}$ it would not have been possible to write a closed form.
In this particular case, where you are (in essence) trying to compute $\sum g(n)$ for a linear function $g(n)=An+B$, the form of $g$ is simple enough that one can recognize it as solvable.  For example, it can be reduced to the calculation of $1+2+\dots + n$, or one can use the fact that for a polynomial of degree $d$, $\quad \sum p(n)$ has a closed form which is a polynomial of degree $d+1$.
This does not explain how those sums were first computed, without knowing in advance that they would be polynomials in $n$. I think that historically this was discovered through computational experience and not some kind of conceptual insight.
A: Yes it is possible. This is an example of a telescoping sequence.
Notice that $d_{n+1} - d_n = n-1$
Now consider
$(d_{n+1} - d_n) + (d_n - d_{n-1}) + (d_{n-1} - d_{n-2}) + \cdots + (d_5 - d_4)$
I will leave the rest to you. 
