Сумма кубов биномиальных коэффициентов (числа Франеля)

[ROFLail]

Всем привет! Сегодня преподаватель дал интересную задачку - найти сумму кубов биномиальных коэффициентов. Посидев некоторое время, решил поискать информацию в Интернете. Нашёл красивое выражение
{S_n}= \sum\limits_{k = 0}^n{{{(C_n^k)}^3}}= \sum\limits_{k = 0}^n{{{(C_n^k)}^2}C_{2k}^n}

Так называемое первое тождество Штреля (если я правильно понял). Кстати, не понимаю, почему в правой части равенства суммирование ведётся от 0, а не от 1. Ведь при $k=0$ для $Sn$ мы получаем множитель $C_0^n=-n$.
Также через некоторое время я нашёл рекуррентное соотношение для этой суммы
${S_n}= \frac{{(7{n^2}- 7n + 2){S_{n - 1}}+ 8{{(n - 1)}^2}{S_{n - 2}}}}{{{n^2}}}$

Однако сколько я не искал, я не смог найти понятного доказательства как для первого равенства, так и для второго. Возможно кто-то из вас знает, доказательство любого из 2ух равенств? Или хотя бы подскажет, где посмотреть/спросить.

[maxal]

Думаю, вам придется читать в серьёзных источниках. См. A000172 и там далее по ссылкам.
Например, рекуррентые соотношения для (обобщённых) чисел Френеля выводятся в статье Cusick (1989).

[pcyanide]

Есть доказательство здесь.

Хитрый способ (делается двойное суммирование, меняется порядок и используются свойства биноминальных коэффициентов), зато довольно понятно.