6
$\begingroup$

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?

  • 0
    Yes sorry, English is my 2nd language. I edited the question2011-09-11

4 Answers 4

10

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.

  • 0
    Thanks, I need to get more familiar with this telescoping idea.2011-09-11
4

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

3

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

2

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.