Supponendo che alla fine della seconda sommatoria ci sia un uno, quindi è questa roba:
distribuendo:
A questo punto, tutto è ridotto a sommatorie di uni; ora, una sommatoria di uni equivale a contare uno per tutti i valori che assume il suo indice, ovvero:
(il +1 è necessario perché la sommatoria itera su tutti i numeri da m a M, estremi compresi); sostituendo quindi questa relazione nella precedente, si ottiene:
ora consideriamo il termine in sommatoria: si può distribuire anche questo; si ha:
Dato che n-1 è indipendente da i, si può portare fuori, e riapplicando la regola di prima si ottiene:
Per quanto riguarda il secondo pezzo, basta ricordare il teorema (si dimostra facilmente per induzione) per cui
allora è immediato che:
Per finire, dunque:
(se non ho sbagliato qualche conto)