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 )