# 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?

-
What do you mean by "proof by inference"? Did you mean proof by induction? – Michael Hardy Sep 11 '11 at 18:01
Yes sorry, English is my 2nd language. I edited the question – Jean-Denis Muys Sep 11 '11 at 19:38

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.

-
Thanks, I need to get more familiar with this telescoping idea. – Jean-Denis Muys Sep 11 '11 at 15:56

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$.

-

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.

-
thanks for this insight. – Jean-Denis Muys Sep 11 '11 at 19:41

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}

-