Mostrar que $\sum_{k=0}^n\binom{3n}{3k}=\frac{8^n+2(-1)^n}{3}$

Question

El otro día un amigo mío me mostró esta suma: $\sum_{k=0}^n\binom{3n}{3k}$. Para encontrar la fórmula explícita he conectado en mathematica y consiguió $\frac{8^n+2(-1)^n}{3}$. Soy curioso en cuanto a cómo se llegaría a esta respuesta.

Mi progreso hasta ahora ha sido limitada. Yo en su mayoría han estado tratando de ver si puedo de alguna manera se relacionan la suma de $$\sum_{k=0}^{3n}\binom{3n}{k}=8^n$$ pero no voy a llegar muy lejos. También he tratado de escribir en el factorial forma, pero eso no ha ayudado mucho.

¿Cómo puedo llegar a la fórmula explícita?

Answer 1

$$f(x)=\sum_0^{3n}{3n\choose r}x^r=(1+x)^{3n}$$ Now let $a,b$ be the nonreal third roots of 1, and evaluate $$f(1)+f(a)+f(b)$$

Answer 2

Se puede demostrar con bastante franqueza por inducción.

Vamos $S_0(n)=\sum_{k\ge 0}\binom{3n}{3k}$, $S_1(n)=\sum_{k\ge 0}\binom{3n}{3k+1}$, y $S_2(n)=\sum_{k\ge 0}\binom{3n}{3k+2}$; a continuación, $$S_0(n)+S_1(n)+S_2(n)=\sum_{k\ge 0}\binom{3n}k=2^{3n}=8^n\;.$$

Ahora

$$\begin{align*} S_0(n)&=\sum_{k\ge 0}\binom{3n}{3k}\\ &=\sum_{k\ge 0}\left(\binom{3n-3}{3k-3}+3\binom{3n-3}{3k-2}+3\binom{3n-3}{3k-1}+\binom{3n-3}{3k}\right)\\ &=\sum_{k\ge 0}\left(\binom{3n-3}{3k-3}+\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}\right)\\ &\qquad\qquad+\sum_{k\ge 0}\left(\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}+\binom{3n-3}{3k}\right)\\ &\qquad\qquad+\sum_{k\ge 0}\left(\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}\right)\\ &=S_0(n-1)+S_1(n-1)+S_2(n-1)\\ &\qquad\qquad+S_0(n-1)+S_1(n-1)+S_2(n-1)\\ &\qquad\qquad+S_1(n-1)+S_2(n-1)\\ &=3\cdot8^{n-1}-S_0(n-1)\\ &=3\cdot8^{n-1}-\frac{8^{n-1}+2(-1)^{n-1}}3\qquad\qquad\text{by the induction hypothesis}\\ &=\frac{8^n-2(-1)^{n-1}}3\\ &=\frac{8^n+2(-1)^n}3\;. \end{align*}$$

Answer 3

$\newcommand{\+}{^{\daga}} \newcommand{\ángulos}[1]{\left\langle\, nº 1 \,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\, nº 1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, nº 1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, nº 1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\piso}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\a la derecha\vert\,} \newcommand{\cy}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left (\, nº 1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\vphantom{\large Un}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, nº 1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $$ \mbox{Nota que}\quad\sum_{k = 0}^{n}{3n \elegir 3k} =\sum_{k = 0}^{\infty}{3n \elegir 3k} $$

\begin{align} &\color{#c00000}{\sum_{k = 0}^{n}{3n \choose 3k}}= \sum_{k = 0}^{\infty}\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{3n} \over z^{3k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{3n} \over z} \sum_{k = 0}^{\infty}\pars{1 \over z^{3}}^{k}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{3n} \over z} {1 \over 1 - 1/z^{3}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1} {z^{2}\pars{1 + z}^{3n} \over z^{3} - 1}\,{\dd z \over 2\pi\ic} \end{align}

El integrando tiene tres polos en el interior del contorno: $\quad\ds{z_{m} \equiv \expo{2m\pi\ic/3}\,,\quad m = -1,0,1}$: \begin{align} &\color{#c00000}{\sum_{k = 0}^{n}{3n \choose 3k}}= \sum_{m = -1}^{1}\lim_{z \to z_{m}} \bracks{\pars{z - z_{m}}\,{z^{2}\pars{1 + z}^{3n} \over z^{3} - 1}} =\sum_{m = -1}^{1}{z_{m}^{2}\pars{1 + z_{m}}^{3n} \over 3z_{m}^{2}} \\[5mm]&={1 \over 3}\sum_{m = -1}^{1}\pars{1 + \expo{2m\pi\ic/3}}^{3n} ={1 \over 3}\sum_{m = -1}^{1}\expo{mn\pi\ic} \pars{\expo{-m\pi\ic/3} + \expo{m\pi\ic/3}}^{3n} \\[5mm]&={8^{n} \over 3}\sum_{m = -1}^{1} \pars{-1}^{mn}\cos^{3n}\pars{m\,{\pi \over 3}} \\[5mm]&={8^{n} \over 3}\bracks{\pars{-1}^{-n}\cos^{3n}\pars{-\,{\pi \over 3}} + 1 + \pars{-1}^{n}\cos^{3n}\pars{\pi \over 3}} ={8^{n} \over 3}\bracks{1 + 2\pars{-1}^{n}\pars{\half}^{3n}} \\[5mm]&={8^{n} \over 3}\bracks{1 + {2\pars{-1}^{n} \over 8^{n}}} \end{align}

$$ \color{#66f}{\large\sum_{k = 0}^{n}{3n \elegir 3k} ={8^{n} + 2\pars{-1}^{n} \over 3}} $$

Answer 4

Voy a tratar de dar una versión más detallada de Gerry Myerson la pista.

Si $S$ es la suma entonces usted tiene $$3S=(1+1)^{3n}+(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n}.$$ (Para obtener este observar que los términos se cancelan. Si usted no está familiarizado con esta forma de escritura de los números complejos, véase Wikipedia.)

Ahora queremos simplificar $(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n}$. Le aviso (por un cálculo directo - es de ayuda si usted dibuja una imagen) que $1+e^{i\frac{2\pi}3}=e^{i\frac\pi3}$$1+e^{i\frac{2\pi}3}=e^{-i\frac\pi3}$. $$(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n} = (e^{i\frac\pi3})^{3n}+(e^{-i\frac\pi3})^{3n}=e^{in\pi}+e^{-in\pi}=(e^{i\pi})^n+(e^{-i\pi})^n.$$ Desde $e^{i\pi}=e^{-i\pi}=-1$, se obtiene $$3S=2^{3n}+2(-1)^n=8^n+2(-1)^n.$$

El truco es muy similar a la que usa $(1+1)^n+(1-1)^n$ para obtener la suma de incluso los coeficientes binomiales, ver a esta pregunta: Evaluar $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$