Simplificación de conminaciones anidados

Question

Dado el siguiente código:

for i = 1 to n
    for j = 1 to i
        for k = j to (i+j)
            r = r + 1
        end
    end
end
print r

Obtengo:

$$ \sum_{i=1}^n\left(\sum_{j=1}^i\left(\sum_{k=j}^{i+j}1\right)\right) = \frac{1}{3}n(n+1)(n+2) $$

el uso de wolfram alpha, puedo llegar a la mano izquierda, pero no tienen idea de cómo llegar a la función de n por mí mismo. De verdad tengo que aprender de esto, pero yo no sé ni lo que el proceso se llama! Los punteros en donde aprender el método se agradece.

Answer 1

Sugerencia

Desde el interior y continuar. El resultado de la mayoría dentro de la suma es sólo ($1+i$) que ahora suma de $j=1$ $j=i$. Así, el resultado de la suma de la media es $i(i+1)$ que es la suma de los números más la suma de sus cuadrados. Por lo tanto, usted debe terminar con la fórmula.

Estoy seguro que usted puede tomar desde aquí.

Answer 2

Podemos utilizar la identidad $$ \sum_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}\etiqueta{1} $$ que se ha comprobado en las respuestas a esta pregunta.

A continuación, calcular $$ \begin{align} \sum_{i=1}^n\sum_{j=1}^i\sum_{k=j}^{i+j}1 &=\sum_{i=1}^n\sum_{j=1}^ii+1\tag{2}\\ &=\sum_{i=1}^ni(i+1)\tag{3}\\ &=\sum_{i=1}^n2\binom{i+1}{2}\tag{4}\\ &=\sum_{i=2}^{n+1}2\binom{i}{2}\tag{5}\\ &=2\binom{n+2}{3}\tag{6}\\ &=\frac{(n+2)(n+1)n}{3}\tag{7} \end{align} $$ Explicación:
$(2)$: y $i+1$ términos de $1$
$(3)$: y $i$ términos de $i+1$
$(4)$: valor de coeficiente binomial
$(5)$: sustitución de $i\mapsto i-1$
$(6)$: aplicar $(1)$
$(7)$: valor de coeficiente binomial

---

Otra Prueba de $\mathbf{(1)}$:

La recursividad que define el Triángulo de Pascales $$ \binom{j+1}{k+1}=\binom{j}{k}+\binom{j}{k+1}\etiqueta{8} $$ Por lo tanto, podemos escribir $$ \begin{align} \sum_{j=k}^n\binom{j}{k} &=\sum_{j=k}^n\left[\binom{j+1}{k+1}-\binom{j}{k+1}\right]\tag{9}\\ &=\sum_{j=k+1}^{n+1}\binom{j}{k+1}-\sum_{j=k}^n\binom{j}{k+1}\tag{10}\\ &=\left(\binom{n+1}{k+1}+\color{#C00000}{\sum_{j=k+1}^n\binom{j}{k+1}}\right) -\left(\binom{k}{k+1}+\color{#C00000}{\sum_{j=k+1}^n\binom{j}{k+1}}\right)\tag{11}\\ &=\binom{n+1}{k+1}-\binom{k}{k+1}\tag{12}\\ &=\binom{n+1}{k+1}\tag{13} \end{align} $$ Explicación:
$\ \:(9)$: Aplicar $(8)$
$(10)$: dividir la suma en dos y volver a indexar la primera ($j\mapsto j-1$)
$(11)$: tire de la $j=n+1$ término de la primera suma y el $j=k$ término de la segunda
$(12)$: cancelar las sumas idénticas
$(13)$: $\binom{k}{k+1}=0$