2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сумма биномиальных коэффициентов кратных трем
Сообщение20.09.2008, 16:12 
Привет!

Мне надо найти сумму
$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 $

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

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

 
 
 
 
Сообщение20.09.2008, 19:16 
3 балла дадут за это, нет?

 
 
 
 
Сообщение20.09.2008, 19:20 
Cave, 3 балла за что?

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

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


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

Cave писал(а):
3 балла дадут за это, нет?


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

 
 
 
 
Сообщение20.09.2008, 21:44 
Аватара пользователя
См. формулу (5) по ссылке: http://mathworld.wolfram.com/SeriesMultisection.html

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

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

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group