一道组合数恒等式

hbghlyj

\[\sum_{k=0}^n\frac{(-1)^k}{2n-k}\binom{2n-k}k=\begin{cases}\frac1n,3|n\\-\frac1{2n},3\nmid n\end{cases}\]

singular

这个是哈代组合恒等式的特殊情况，奥赛经典组合卷第二章算子方法

tommywong

这个是哈代组合恒等式的特殊情况，奥赛经典组合卷第二章算子方法
singular90 发表于 2020-6-27 11:01

第三張圖喺度遊花園，我三步搞撚掂

$\displaystyle [x^{m-1}]\frac{1+2x}{1+x+x^2}=[x^{m-1}]\frac{(1+2x)(1-x)}{1-x^3}$
$\displaystyle =[x^{m-1}](1+x-2x^2)\sum_{n=0}^\infty x^{3n}
=\begin{cases}-2 & m\equiv 0\pmod{3}\\
1 & m\equiv 1,2\pmod{3}\end{cases}$

tommywong

我咁撚樣仲好

$\displaystyle S_m=\sum_{k=0}^\infty (-1)^k \binom{m-k}{k},~S_0=1,~S_1=1,~S_2=0$

$\displaystyle S_{m+1}=\sum_{k=0}^\infty (-1)^k \binom{m+1-k}{k}
=1+\sum_{k=1}^\infty (-1)^k \left(\binom{m-k}{k}+\binom{m-k}{k-1}\right)$
$\displaystyle =\sum_{k=0}^\infty (-1)^k \binom{m-k}{k}-\sum_{k=0}^\infty (-1)^k \binom{m-1-k}{k}$
$=S_m-S_{m-1}=S_{m-1}-S_{m-2}-S_{m-1}=-S_{m-2}$

$S_m=\begin{cases}
1 & m\equiv 0\pmod{6}\\
1 & m\equiv 1\pmod{6}\\
0 & m\equiv 2\pmod{6}\\
-1 & m\equiv 3\pmod{6}\\
-1 & m\equiv 4\pmod{6}\\
0 & m\equiv 5\pmod{6}
\end{cases}
=\begin{cases}
(-1)^m & m\equiv 0\pmod{3}\\
-(-1)^m & m\equiv 1\pmod{3}\\
0 & m\equiv 2\pmod{3}\\
\end{cases}$

$\displaystyle \frac{1}{m-k}\binom{m-k}{k}=\frac{1}{m}\left(\binom{m-k}{k}+\binom{m-2-(k-1)}{k-1}\right)$

$\displaystyle \sum_{k=0}^\infty (-1)^k \frac{1}{m-k}\binom{m-k}{k}
=\frac{1}{m}\sum_{k=0}^\infty (-1)^k\binom{m-k}{k}
+\frac{1}{m}\sum_{k=1}^\infty (-1)^k\binom{m-2-(k-1)}{k-1}$
$\displaystyle =\frac{S_m-S_{m-2}}{m}=\frac{S_{m+1}+S_m}{m}
=\begin{cases}
\frac{2}{m} & m\equiv 0\pmod{6}\\
\frac{1}{m} & m\equiv 1\pmod{6}\\
\frac{-1}{m} & m\equiv 2\pmod{6}\\
\frac{-2}{m} & m\equiv 3\pmod{6}\\
\frac{-1}{m} & m\equiv 4\pmod{6}\\
\frac{1}{m} & m\equiv 5\pmod{6}\\
\end{cases}
=\begin{cases}
\frac{2(-1)^m}{m} & m\equiv 0\pmod{3}\\
\frac{-(-1)^m}{m} & m\equiv 1\pmod{3}\\
\frac{-(-1)^m}{m} & m\equiv 2\pmod{3}\\
\end{cases}$