la forma cerrada para $d(4)=2$, $d(n+1)=d(n)+n-1$?

Question

Estoy ayudando a un amigo en su último año de la escuela secundaria con su clase de matemáticas. Se están estudiando las recurrencias y la prueba por inferencia. Uno de los ejercicios era simplemente "¿cuántas diagonales se hace un regular $n$-polígono?".

Rápidamente encontramos una respuesta directa a esa pregunta: $d(n) = \frac{(n-3)n}2$, pero ya se están estudiando las recurrencias, no paramos, y encontró la recurrencia $d(n+1)=d(n)+n-1$. Se procedió a probar por inducción que la forma cerrada en un principio nos encontramos es de hecho una solución para la recurrencia.

Pero entonces él me hizo una pregunta que no podía responder: hemos encontrado la forma cerrada debido a que la pregunta nos da una asignación obvia para un fácil resolver la geometría del problema, pero hay una manera de encontrar una forma cerrada mediante la recurrencia sólo?

Answer 1

Sí es posible. Este es un ejemplo de una telescópica de la secuencia.

Observe que $d_{n+1} - d_n = n-1$

Ahora considere la posibilidad de

$(d_{n+1} - d_n) + (d_n - d_{n-1}) + (d_{n-1} - d_{n-2}) + \cdots + (d_5 - d_4)$

Voy a dejar el resto para usted.

Answer 2

Usted puede pensar en su recurrencia como una diferencia de ecuaciones, indicando que $$ d(n+1)-d(n)=n-1, $$ con algunos condición inicial. En algún momento (siglo 18, por ejemplo), la gente sabía mucho acerca de la diferencia de las secuencias. En particular, si la diferencia de la secuencia es un polinomio de grado $k$, entonces el original es un polinomio de grado $k+1$ (y viceversa). Incluso hay una fórmula que le dan los coeficientes, pero si usted es perezoso, usted puede simplemente escribir (en este caso) $$ d(n) = An^2 + Bn + C, $$ sustituir algunos pequeños $n$, y resolver para $A,B,C$.

Answer 3

hemos encontrado la forma cerrada debido a que la pregunta nos da una asignación obvia para un fácil resolver la geometría del problema, pero hay una manera de encontrar una forma cerrada mediante la recurrencia sólo?

En general no hay ninguna forma cerrada, similar a la falta de una forma cerrada para las integrales de funciones de cálculo. Si hay recurrencia había sido $d(n+1)-d(n)=2^{n^2}$ no habría sido posible escribir de una forma cerrada.

En este caso particular, donde está (en esencia) tratando de calcular $\sum g(n)$ de una función lineal $g(n)=An+B$, la forma de $g$ es bastante sencilla que se puede reconocer como posible solución. Por ejemplo, puede ser reducido para el cálculo de $1+2+\dots + n$, o uno puede usar el hecho de que para un polinomio de grado $d$, $\quad \sum p(n)$ tiene una forma cerrada que es un polinomio de grado $d+1$. Esto no explica cómo esas sumas fueron calculadas primero, sin saber de antemano que iban a ser polinomios en $n$. Creo que, históricamente, este fue descubierto a través de la experiencia computacional y no algún tipo de visión conceptual.

Answer 4

Como ha sido señalado, $d(n+1)-d(n)=n-1$, o lo que es equivalente, $d(n)-d(n-1)=n-2$. La inversa de la diferencia finita operador de suma, como la inversa de la derivada es la integración. Para ser precisos: $$ \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} $$ Hay muchos enfoques para calcular la suma de $(1)$. Uno de los más simples, comúnmente atribuido a Gauss como un niño, es: $$ \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} $$ hay $n-4$ columnas, por lo que el doble de la suma es $(n-4)(n+1)$. Por lo tanto, $$ \begin{align} d(n)&=2+\frac{(n-4)(n+1)}{2}\\ &=\frac{n^2-3n}{2} \end{align} $$