Prueba combinatoria de $a^n - b^n = (a - b)(a^{n – 1} + a^{n – 2}b + \dots + ab^{n – 2} + b^{n – 1})$

Question

¿Es posible presentar un argumento combinatorio que demuestre la siguiente identidad?

$$a^n - b^n = (a - b)(a^{n – 1} + a^{n – 2}b + \dots + ab^{n – 2} + b^{n – 1})$$

Mi idea era esta:

Considere el número de formas $N$ para distribuir $n$ bolas numeradas en $a$ casillas numeradas de tal manera que debe haber al menos $1$ balón entre los primeros $a - b$ cajas. El número de formas de hacerlo es tomar el número total de formas sin restricción, y restar el número de formas en que todas las bolas se distribuyen sólo entre las últimas $b$ cajas. Eso es,

$$N = a^n - b^n$$

Como alternativa, podemos elegir primero al menos $1$ bola(s) y distribuirlas entre los primeros $a - b$ cajas, y luego distribuir las bolas restantes entre los últimos $b$ cajas. Eso es,

$$N = \binom{n}{1}(a-b)b^{n-1} + \binom{n}{2}(a-b)^2b^{n-2} + \dots + \binom{n}{n}(a-b)^nb^0$$

Sin embargo, esto no se asemeja a lo requerido $RHS$ de la identidad.

Answer 1

Que la pelota $k$ será la bola de mayor número que se coloque en una de las primeras $a-b$ cajas. Entonces todas las bolas numeradas $k+1$ a través de $n$ se colocan en el último $b$ cajas, mientras que las bolas numeradas $1$ a través de $k-1$ puede colocarse en cualquiera de los $a$ cajas.

Answer 2

Usando la fórmula binomial:

$a^n - b^n = (a-b+b)^n - b^n = \sum_{k=0}^{n-1}{n\choose k}(a-b)^{n-k}b^k = (a-b)(\sum_{k=0}^{n-1}{n\choose k}(a-b)^{n-k-1}b^k)$

Y $$\sum_{k=0}^{n-1}{n\choose k}(a-b)^{n-k-1}b^k = \sum_{k=0}^{n-1} \sum_{j=0}^{n-k-1}{n\choose k}{n-k-1\choose j}(-1)^ja^{n-k-1-j}b^{j+k} = \sum_{i=0}^{n-1}(\sum_{j+k=i} {n\choose k}{n-k-1\choose j}(-1)^j)a^{n-1-i}b^i$$

Tenemos que demostrar $\sum_{j+k=i} {n\choose k}{n-k-1\choose j}(-1)^j = 1$ es decir $\sum_{j=0}^i{i\choose j}\frac{(-1)^j}{n-(i-j)} = \dfrac{1}{{n \choose i}(n-i)}$

Esto se puede demostrar con descomposición parcial de la fracción combinado con el hecho de que $\sum_{j=0}^n(-1)^{n-j}{n\choose j} = 0$ .

La descomposición parcial dice $$\begin{align} \dfrac{1}{{n\choose i}} &= -\sum_{j=0}^{i}(-1)^{i-j}{i \choose j}\frac{i-j}{n-j} \\ &= -\sum_{j=0}^{i}(-1)^{i-j}{i \choose j}\frac{i-n}{n-j} - \sum_{j=0}^{i}(-1)^{i-j}{i \choose j}\frac{n-j}{n-j} \\ &= -\sum_{j=0}^{i}(-1)^{i-j}{i \choose j}\frac{i-n}{n-j} \\ \end{align}$$ que da la conclusión $$\begin{align} \dfrac{1}{{n\choose i}(n-i)} = \sum_{j=0}^{i}(-1)^{i-j}{i \choose j}\frac{1}{n-j} = \sum_{j=0}^{i}(-1)^{j}{i \choose j}\frac{1}{n-(i-j)} \end{align}$$

Evidentemente, si hacemos las cosas en sentido inverso, podemos demostrar la descomposición de la fracción parcial con $(a^n -b^n)= (a-b)(a^{n-1} + \cdots + b^{n-1})$ .