Probando $\sum \limits_{i=1}^k n_i^2 \le n^2 -(k-1)(2n-k) $

Question

Dada, $\sum \limits_{i=1}^k n_i = n$ y $n_i \ge 1$ . Demostrar que $$\sum \limits_{i=1}^k n_i^2 \le n^2 -(k-1)(2n-k) $$

Me encuentro con algunos problemas para entender el siguiente paso de este prueba:

$$ \left(\sum \limits_{i=1}^k (n_i-1)\right)^2 = \sum \limits_{i=1}^k (n_i^2-2n_i)+k+ \text{ non-negative cross terms } $$

No estoy entendiendo esta transformación, ¿alguien podría explicar esto de manera lúcida?

Fuente: Esta prueba se da en Teoría de grafos con aplicaciones . Página 23

Answer 1

Todo se reduce al hecho de que

$$\begin{align*} \left(\sum_{i=1}^ka_i\right)^2&=(a_1+\ldots+a_k)^2\\\\ &=a_1(a_1+\ldots+a_k)+a_2(a_1+\ldots+a_k)+\ldots+a_k(a_1+\ldots+a_k)\\\\ &=\sum_{j=1}^k\left(a_j\sum_{i=1}^ka_i\right)\\\\ &=\sum_{j=1}^k\sum_{i=1}^ka_ja_i\;. \end{align*}$$

Para cada par ordenado $\langle j,i\rangle$ de subíndices se obtiene un término $a_ja_i$ . Claramente $k$ de esos son los términos cuadrados $a_1^2,\dots,a_k^2$ . Los otros vienen en parejas: si $j\ne i$ Entonces se obtienen los dos $a_ja_i$ y $a_ia_j$ . Así,

$$\left(\sum_{i=1}^ka_i\right)^2=\sum_{i=1}^ka_i^2+2\sum_{1\le i<j\le k}a_ia_j\;.\tag{1}$$

En su caso $a_i=n_i-1$ Así que $a_i^2=n_i^2-2n_i+1$ y

$$\sum_{i=1}^ka_i^2=\sum_{i=1}^k\left(n_i^2-2n_i+1\right)=\sum_{i=1}^k\left(n_i^2-2n_i\right)+\sum_{i=1}^k1=\sum_{i=1}^k\left(n_i^2-2n_i\right)+k\;.$$

El resto de $(1)$ es una suma de productos $a_ia_j$ que en su entorno son productos $(n_i-1)(n_j-1)$ y como cada $n_i\ge 1$ Estos productos son todos no negativos.