Сумма биномиальных коэффициентов кратных трем

[Покоритель курумника]

Привет!

Мне надо найти сумму
$C_{n}^{0} + C_{n}^{3} + C_{n}^{6} + \ldots$

Я попробовал расписать эту сумму два раза при помощи правила

$C_{n}^{k} = C_{n-1}^{k-1} + C_{n-1}^{k} $

Получилось следующее

$\sum\limits _{k=0}^{[\frac{n}{3}]} C_{n}^{3k} = \sum\limits _{k=0}^{[\frac{n}{3}]} (C_{n-2}^{3k-2} + 2C_{n-2}^{3k-1} + C_{n-2}^{3k}) =\\ \sum\limits _{k=0}^{n-2} C_{n-2}^{k} + \sum\limits _{k=0}^{[\frac{n}{3}]} (C_{n-2}^{3k-1} = 2^{n-2} + \sum\limits _{k=0}^{[\frac{n}{3}]}C_{n-2}^{3k-1} $

Потом провернув эту операцию по отношению к правому слагаемому еще 2 раза, получил
$\sum\limits _{k=0}^{[\frac{n}{3}]} C_{n}^{3k} = 2^{n-2} + 2^{n-4} + 2^{n-6} + \sum\limits _{k=0}^{[\frac{n-6}{3}]} C_{n-6}^{3k} $

Т.е. получается рекуррентное соотношение вида
$x_{n} = \frac{21}{64}2^{n} + x_{n-6} $
$x_{0} = x_{1} = x_{2} = 1 $
$x_{3} = x_{4} = x_{5} = 2 $

Его я тоже попробовал решить, найти производящую функцию, но ничего хорошего тут не вышло, да и вообще я чувствую, что намудрил, всё должно решаться как-то проще...

[V.V.]

Используйте то, что в формулу $(1+x)^n=\sum\limits_{k=0}^n C_n^k x^k$ можно подставлять и комплексные числа.

[Cave]

3 балла дадут за это, нет?

[V.V.]

Cave, 3 балла за что?

[Cave]

V.V.
Это автору вопрос был.
Видел на прошлой неделе эту задачу (хотя и ясно, что она известная и популярная) в одном листке одного, так сказать, учебного места, там за неё аж 3 балла давали. Вот и решил уточнить.

[Покоритель курумника]

V.V. писал(а):

Используйте то, что в формулу $(1+x)^n=\sum\limits_{k=0}^n C_n^k x^k$ можно подставлять и комплексные числа.

Попробовал подставить $x=i$, $x=-i$, вычесть/сложить получившиеся выражения, но максимум что могу найти из этого - сумму знакочередующихся четных и нечетных коэффициентов. Как найти кратные трем, всё равно не ясно, к сожалению.

Cave писал(а):

3 балла дадут за это, нет?

Да, 3 балла дадут, Вы угадали . Нарешал на 28, пока не хватает...

[maxal]

См. формулу (5) по ссылке: http://mathworld.wolfram.com/SeriesMultisection.html

[Cave]

Если вкратце - подставьте вместо x кубические корни из плюс-минус единицы, поскладывайте - и получится.

[Покоритель курумника]

Спасибо всем за помощь, всё получилось! Подставил $x=1,x=e^{2\pi i/3}, x=e^{4\pi i/3}$ и сложил получившиеся три равенства. Все коэффиценты при некратных трем обнулились. И получился ответ как на mathworld.