Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

4 Answers 4

up vote 10 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this 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?

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.

share|improve this answer
    
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} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.