combinatorial identity ทางออกอื่น?
ฉันจะขอบคุณถ้ามีใครสามารถช่วยฉันแก้ปัญหาต่อไปนี้:
ฉันต้องแสดงให้เห็นว่า $$\sum^{33}_{k=0}\binom{100}{3k}=\sum^{49}_{k=0}4^k$$
หลักฐานของฉันมีดังต่อไปนี้: $$(1+x)^{100} = a_0 + a_1x + a_2x^2 + \cdots + a_{100}x^{100}$$
ปล่อย $A = a_0 + a_3 + a_6 + \cdots + a_{99}, B = a_1 + a_2 + a_4 + a_5 + a_7 + a_8 + \cdots + a_{98} + a_{100}$$
แล้ว $$A+B = 2^{100}$$
$$x^3=1 \to x=1,w,w^2$$
$x$ ใส่ $w$, $w^2$ และผลรวม
$$\begin{align*} (1+w)^{100} + (1+w^2 )^{100} &=w^{200} + w^{100}\\ &=w^{2} + w\\ &=-1\\ &= 2A + a_1(w+w^2) + a_2(w^2 + w^4) + a_4(w^4 + w^8) + \cdots + a_{100}(w^{100} + w^{200}) \\ &= 2A - B \end{align*}$$
ดังนั้น $$A+B = 2^{100}, 2A - B=-1$$
$$A = \frac{2^{100} - 1}{3} = \frac{4^{50} - 1}{3} =\sum^{49}_{k=0}4^k $$
แต่ฉันต้องการทราบว่ามีหลักฐานอื่นสำหรับปัญหานี้หรือไม่
คำตอบ
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$คำตอบของฉันเป็นอย่างใดคล้ายกับหนึ่งโดย$\ds{\tt @Joshua\ P.\ Swanson}$. แต่มีบางอย่างที่แตกต่างกัน\begin{align} &\bbox[5px,#ffd]{\sum_{k = 0}^{33}{100 \choose 3k}} = \sum_{k = 0}^{99}{100 \choose k}{1 + \expo{2k\pi\ic/3} + \expo{-2k\pi\ic/3} \over 3} \\[5mm] = &\ {1 \over 3}\sum_{k = 0}^{99}{100 \choose k} + {2 \over 3}\,\Re\sum_{k = 0}^{99}{100 \choose k} \pars{\expo{2\pi\ic/3}}^{k} \\[5mm] = &\ {1 \over 3}\pars{2^{100} - 1} + {2 \over 3}\,\Re\bracks{\pars{1 + \expo{2\pi\ic/3}}^{100} - \expo{200\pi\ic/3}} \\[5mm] = &\ {2^{100} \over 3} + {2 \over 3}\,\Re\bracks{\pars{{1 \over 2} + {\root{3} \over 2}\,\ic}^{100}} \\[5mm] = &\ {2^{100} \over 3} + {2 \over 3}\,\Re\bracks{\pars{\expo{\ic\pi/3}}^{100}} = {2^{100} \over 3} + {2 \over 3}\cos\pars{100\pi \over 3} \\[5mm] = &\ {2^{100} \over 3} - {1 \over 3} = {4^{50} - 1 \over 4 - 1} = \bbx{\sum_{k = 0}^{49}4^{k}} \\ & \end{align}
อาร์กิวเมนต์ของฉันใช้การแปลงฟูเรียร์แบบไม่ต่อเนื่องมากหรือน้อยในวิธีมาตรฐานเพื่อเลือกค่าสัมประสิทธิ์ที่สามทุกค่า ปล่อย$\zeta_3 = \exp(2\pi i/3)$เป็นรากที่ 3 ดั้งเดิมของความสามัคคี โปรดทราบว่า$1^k + \zeta_3^k + \zeta_3^{2k} = 3\delta_{3 \mid k}$. การปล่อย$p(x) := (1+x)^{100}$, ที่เราเห็น $$\begin{align*} \frac{p(1)+p(\zeta_3)+p(\zeta_3^2)}{3} = \frac{1}{3} \sum_{k=0}^{100} \binom{100}{k} (1^k + \zeta_3^k + \zeta_3^{2k}) = \sum_{k=0}^{33} \binom{100}{3k}.\end{align*}$$
ในทางกลับกัน, $p(1)=2^{100}$ และ $p(\zeta_3) = (1+\zeta_3)^{100}$. ดังที่ทราบกันดีว่า$1, \zeta_3, \zeta_3^2$ สร้างจุดยอดของสามเหลี่ยมด้านเท่าและ $1+\zeta_3, -1, 1+\zeta_3^2$สร้างจุดยอดที่เหลือของรูปหกเหลี่ยมปกติ อย่างไรก็ตาม,$1+\zeta_3$ มีมุมเชิงขั้วของ $\pi/3$. ดังนั้น$(1+\zeta_3)^{100}$ มีมุมเชิงขั้วของ $100\pi/3 \equiv 4\pi/3$ และขนาดของ $1$. ในทำนองเดียวกัน$(1+\zeta_3^2)^{100}$ มีมุมเชิงขั้วของ $-4\pi/3$ และขนาดของ $1$. ดังนั้น$p(\zeta_3) + p(\zeta_3^2) = 2\cos(4\pi/3) = -1$. ทางซ้ายมือคือ$$\begin{align*}\frac{2^{100} - 1}{3} &= \frac{4^{50} - 1}{4 - 1} = \sum_{i=0}^{49} 4^i\end{align*}$$
(หมายเหตุ: ฉันเขียนสิ่งนี้ในขณะที่การโต้แย้งของคุณไม่สามารถอ่านได้ดูเหมือนว่าจะคล้ายกันในแง่จิตวิญญาณ)