等差组合数求和

fungarwai

$\sum_{i=1}^n C_{2i-1}^m=(\frac{-1}{2})^m (n-\sum_{i=0}^{m-1} (-2)^i C_{2n+1}^{i+2})$

$\sum_{i=1}^n C_{2i}^m=C_{2n+1}^{m+1}-C_1^{m+1}+(\frac{-1}{2})^m (\sum_{i=0}^{m-1} (-2)^i C_{2n+1}^{i+2}-n)$

$\sum_{i=1}^n C_{a+di}^m=?$

Lwins_G

以\( \sum_{j=0}^n \binom{m}{jd} \)为例，我简要说一下做法吧。

构造母函数
$$ f(x) = \sum_{j=0}^{nd} \binom{j}{m} x^j. $$
（提示，\( f(x) = \dfrac{P(x)}{(1-x)^{m+1}} \)，其中$P(x)$是多项式）

那么我们就有
$$ \sum_{j=0}^n \binom{m}{jd} = \frac{1}{n} \sum_{j=1}^n f(\omega^j). $$
其中`\omega`是`n`次单位根。

fungarwai

Lwins_G 发表于 2014-1-8 14:02
以\( \sum_{j=0}^n \binom{m}{jd} \)为例，我简要说一下做法吧。

构造母函数

$(1+1)^{2m}=\sum_{j=0}^{2m} C_{2m}^j,(1-1)^{2m}=\sum_{j=0}^{2m} C_{2m}^j (-1)^j$
$2^{2m}=2\sum_{j=0}^m C_{2m}^{2j}$
这个我明白
$\sum_{j=0}^n C_m^{2j}$要怎么弄？那个P(x)取什么？

Lwins_G

fungarwai 发表于 2014-1-9 08:30
$(1+1)^{2m}=\sum_{j=0}^{2m} C_{2m}^j,(1-1)^{2m}=\sum_{j=0}^{2m} C_{2m}^j (-1)^j$
$2^{2m}=2\sum_{j ...

提供一下我的思路，
注意到
$$ \begin{split} f(x) =& \sum_{j=0}^{\infty} \binom{j}{m} x^j - \sum_{j=nd+1}^{\infty} \binom{j}{m} x^j \\ =& g(x) - h(x) \end{split}$$
显然\( g(x) = \dfrac{1}{(1-x)^{m+1}} \)而\( h(x) \)为\( x ^ {nd + 1} g(x) \)再乘一\( m \)次多项式。请试一试自己推导系数吧 : )

fungarwai

看看能不能算下去

$d\sum_{i=0}^n C_{a+di}^m=C_{a+1+dn}^{m+1}-C_a^{m+1}+\sum_{r=1}^{d-1} (\frac{1}{1-e^{\frac{2\pi r}{d}i}})^{m+1} \sum_{k=0}^m (e^{-\frac{2\pi r}{d}i} C_a^k-C_{a+1+dn}^k)(e^{-\frac{2\pi r}{d}i}-1)^k$

fungarwai

$d\sum_{i=0}^n C_{a+di}^m=C_{a+1+dn}^{m+1}-C_a^{m+1}+ \sum_{k=0}^m (C_a^k\sum_{r=1}^{d-1} (e^{\frac{2\pi r}{d}i})^{-k-1} (1-e^{\frac{2\pi r}{d}i})^{k-m-1}-C_{a+1+dn}^k\sum_{r=1}^{d-1} (e^{\frac{2\pi r}{d}i})^{-k} (1-e^{\frac{2\pi r}{d}i})^{k-m-1}) $

求$\sum_{r=1}^{d-1} (e^{\frac{2\pi r}{d}i})^{-k-1} (1-e^{\frac{2\pi r}{d}i})^{k-m-1}$、$\sum_{r=1}^{d-1} (e^{\frac{2\pi r}{d}i})^{-k} (1-e^{\frac{2\pi r}{d}i})^{k-m-1}$

fungarwai

$\sum_{k=0}^n C_{a+dk}^m=\sum_{r=0}^{d-1} (C_{m+1+n+[\frac{a}{d}]-r}^{m+1}-C_{m+[\frac{a}{d}]-r}^{m+1})\sum_{k=0}^{m+1} (-1)^k C_{m+1}^k C_{m+(a-m)remd+dr-dk}^m$

$\sum_{k=0}^2 C_{3+7k}^3=\sum_{r=0}^6 C_{6-r}^4 \sum_{k=0}^4 (-1)^k C_4^k C_{3+7r-7k}^3=C_6^4+(C_{10}^3-4C_3^3)C_5^4+(C_{17}^3-4C_{10}^3+6C_3^3)C_4^4=15+(116)5+206=801$