identité combinatoire une autre solution?

Question

J'apprécierais que quelqu'un puisse m'aider avec le problème suivant:

J'ai besoin de montrer ça, $$\sum^{33}_{k=0}\binom{100}{3k}=\sum^{49}_{k=0}4^k$$

Ma preuve est la suivante: $$(1+x)^{100} = a_0 + a_1x + a_2x^2 + \cdots + a_{100}x^{100}$$

Laisser $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}$$

puis $$A+B = 2^{100}$$

$$x^3=1 \to x=1,w,w^2$$

$x$ mettre $w$, $w^2$ et somme

$$\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*}$$

donc $$A+B = 2^{100}, 2A - B=-1$$

$$A = \frac{2^{100} - 1}{3} = \frac{4^{50} - 1}{3} =\sum^{49}_{k=0}4^k $$

Mais je veux savoir s'il existe une autre preuve de ce problème.

Answer 1

$\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}$Ma réponse est en quelque sorte similaire à celle de$\ds{\tt @Joshua\ P.\ Swanson}$. Cependant, il existe quelques différences .\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}

Answer 2

Mon argument utilise plus ou moins une transformée de Fourier discrète de manière standard pour enlever chaque troisième coefficient. Laisser$\zeta_3 = \exp(2\pi i/3)$être une troisième racine primitive de l'unité. Notez que$1^k + \zeta_3^k + \zeta_3^{2k} = 3\delta_{3 \mid k}$. Location$p(x) := (1+x)^{100}$, nous voyons $$\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*}$$

D'autre part, $p(1)=2^{100}$ et $p(\zeta_3) = (1+\zeta_3)^{100}$. Comme il est bien connu,$1, \zeta_3, \zeta_3^2$ forment les sommets d'un triangle équilatéral, et $1+\zeta_3, -1, 1+\zeta_3^2$forment les sommets restants d'un hexagone régulier. En tous cas,$1+\zeta_3$ a un angle polaire de $\pi/3$. Par conséquent$(1+\zeta_3)^{100}$ a un angle polaire de $100\pi/3 \equiv 4\pi/3$ et une magnitude de $1$. également$(1+\zeta_3^2)^{100}$ a un angle polaire de $-4\pi/3$ et une magnitude de $1$. Par conséquent$p(\zeta_3) + p(\zeta_3^2) = 2\cos(4\pi/3) = -1$. Donc, le côté gauche est$$\begin{align*}\frac{2^{100} - 1}{3} &= \frac{4^{50} - 1}{4 - 1} = \sum_{i=0}^{49} 4^i\end{align*}$$

(Remarque: j'ai écrit ceci alors que votre argument était illisible. Ils semblent être similaires dans l'esprit.)