Проделайте то, что советует
Brukvalub, для

, и поймете механизм, по которому можно построить и общую формулу. У меня получилась такая общая формула:

.
(Здесь

- биномиальные коэффициенты и считается, что

-кратной суммы при

просто нет.)
Оттуда же будет виден способ, как доказать эту формулу по индукции.