Show that $ \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k $ is divisible by $2^n$

Question

I want to prove that $$ \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k = \sum_{k=0}^{2n} \binom{2n}{k} 3^{\lceil k/2 \rceil} $$ is divisible by $2^n$.

I tried induction the following way \begin{align*} \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k & = \sum_{k=0}^{n} \left( \binom{2n}{2k-1} + \binom{2n}{2k} \right) 3^k \\ & = \sum_{k=0}^{n} \left( \binom{2n-1}{2k-2} + \binom{2n-1}{2k-1} + \binom{2n-1}{2k-1} + \binom{2n-1}{2k} \right) 3^k \\ & = 4\cdot \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k} 3^k + 2\sum_{k=0}^n \binom{2n-1}{2k-1} 3^k \end{align*} now I can apply the induction hypothesis to the first part, hence the entire first summand is divisible by $2^{n+1}$, if I can show that $$ \sum_{k=0}^n \binom{2n-1}{2k-1} 3^k $$ is divisble by $2^{n-1}$ I would be done. But here I failed.

So do you have any hints how to show the original claim?

EDIT: As mentioned by Will Orrick in the comments, the inductive approach works too, just prove the stronger claim that $$ \sum_{k=0}^{n}\binom{2n}{2k}3^k, \quad \sum_{k=0}^{n}\binom{2n+1}{2k}3^k, \quad \sum_{k=0}^{n}\binom{2n+1}{2k+1}3^k, \quad \sum_{k=0}^{n}\binom{2n}{2k+1}3^k \quad $$ are all divisible by $2^n$. If $n = 1$ we get $4$, $10$, $6$ and $2$ and if $n > 1$ we have \begin{align*} & \sum_{k=0}^{n}\binom{2n}{2k}3^k \\ & = 3 \sum_{k=0}^n \binom{2(n-1)+1}{2(k-1)+1} 3^{k-1} + \sum_{k=0}^n \binom{2(n-1)+1}{2k} 3^k \\ & = 3 \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k+1} 3^k + \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k} 3^k \\ & = 3 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + 3 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k+1} 3^k + \sum_{k=0}^{n-1} \binom{2(n-1)}{2k-1} 3^k + \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + 3 \sum_{k=0}^{n-2} \binom{2(n-1)}{2k+1} 3^k + \sum_{k=1}^{n-1} \binom{2(n-1)}{2k-1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + \sum_{k=1}^{n-1} \binom{2(n-1)}{2k-1} 3^k + \sum_{k=1}^{n-1} \binom{2(n-1)}{2k-1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + 6\sum_{k=0}^{n-2} \binom{2(n-1)}{2k+1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + 6\sum_{k=0}^{n-1} \binom{2(n-1)}{2k+1} 3^k \end{align*} and now by assumption both sums are divisible by $2^{n-1}$, and as they are multiplied with even numbers their sum is divisible by $2^n$. Similar \begin{align*} \sum_{k=0}^{n}\binom{2n+1}{2k}3^k & = \sum_{k=0}^n \left( \binom{2n-1}{2k-2} + \binom{2n-1}{2k-1} + \binom{2n-1}{2k-1} + \binom{2n-1}{2k } \right) 3^k \\ & = \sum_{k=1}^n \binom{2n-1}{2k-2} 3^k + \sum_{k=0}^{n-1} \binom{2n-1}{2k} 3^k + 2\sum_{k=1}^n \binom{2n-1}{2k-1} 3^k \\ & = 3 \sum_{k=0}^{n-1} \binom{2n-1}{2k} 3^k + \sum_{k=0}^{n-1} \binom{2n-1}{2k} 3^k + 2\sum_{k=1}^n \binom{2n-1}{2k-1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2n-1}{2k} 3^k + 2\sum_{k=1}^n \binom{2n-1}{2k-1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k} 3^k + 6\sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k+1} 3^k \\ \end{align*} and for the other sums we have \begin{align*} \sum_{k=0}^{n}\binom{2n+1}{2k+1}3^k & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k+1} 3^k + 2\sum_{k=0}^n \binom{2n-1}{2k} 3^k\\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k+1} 3^k + 2\sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k} 3^k\\ \sum_{k=0}^{n}\binom{2n}{2k+1}3^k & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k+1} 3^k + 2\sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k \end{align*} and the induction hypothesis gives the result.

Answer 1

Let there be a string of $2n$ lights. Suppose that each light may be off or may shine in one of three colors, red, green, or blue, and that a string of lights is made to shine in a particular color by bracketing it with a pair of control blocks of that color. Suppose further that at most one control block may be inserted between two adjacent lights (also before the first light and after the last light). Note that control blocks are inserted in same-color pairs, with no control blocks in between, and that it follows from these rules that each string of shining lights must be followed by at least one off light (except at the end). Some examples are shown below.

|GG|O|G|O|B|

OOO|RR|OO|BBBB|O

There are $2n+1$ positions at which control blocks may be placed. There must be an even number, say $2k$, of control blocks, and there are $\binom{2n+1}{2k}$ ways of placing $2k$ control blocks. There are $3^k$ ways of choosing the colors of the $k$ pairs of adjacent control blocks. Therefore the total number of configurations for $2n$ lights is $$ \sum_{k=0}^n\binom{2n+1}{2k}3^k. $$

Now consider adding two lights at the right end of a string. If a configuration ends with a control block, there are four ways to extend the configuration,

...*| + OO

...*| + O|R|

...*| + O|G|

...*| + O|B|

where * stands for R, G, or B. One can also move the existing control block one or two units to the right,

...* + *|O

...* + **|

(All *s take the same value, R, G, or B.) So there are six ways to extend a configuration that ended in a control block.

If the configuration did not end in a control block, there are $10$ possibilities,

...O + OO

...O + |*|O

...O + |**|

...O + O|*|

where, again, * takes one of three values, R, G, B. Since every configuration of $2n$ lights gives rise to an even number of configurations of $2n+2$ lights, the number of configurations of $2n$ lights is divisible by $2^n$.

Answer 2

$$2S(n)=(1+\sqrt3)^{2n+1}+(1-\sqrt3)^{2n+1}=(4+2\sqrt3)^n(1+\sqrt3)+(4-2\sqrt3)^n(1-\sqrt3)$$

$$\implies S(m+2)-\{(4+2\sqrt3)+(4-2\sqrt3)\}S(m+1)+(4+2\sqrt3)(4-2\sqrt3)S(m)=0$$

Answer 3

My approach was to look at the values, see if I can find some pattern. First couple of values are $1,10,76,568,4240,\dots$. You can check that this is a sequence A107903, and it has known generating function $$ f(x)=\frac{1+2x}{1-8x+4x^2}. $$ Now from this you can easily derive recurrence formula by multiplying both sides by $(1-8x+4x^2)$ and comparing the coefficients (taking $f(x)=\sum a_nx^n$). By this method we get $$a_0=1,a_1=10$$ $$a_n=8a_{n-1}-4a_{n-2}$$ From this it is quite straight forward to prove the claim by induction.

Only thing that might be a little unclear is how to get that generating function in the first place, and I will think about that, but you could arrive at the recurrence by other means as well (such as assuming there is a linear recurrence and finding its coefficients).

Answer 4

I think it's worth pointing out that the standard trick in play here, which gives us the $$ \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k = \frac{1}{2}\left((1+\sqrt3)^{2n+1}+(1-\sqrt3)^{2n+1}\right) $$ formula found in other answers, is to apply the binomial theorem to $(x+y)^n$ and $(x-y)^n$ and add these up. Here, we have \begin{align} (1 + \sqrt3)^{2n+1} &= \sum_{j=0}^{2n+1} \binom{2n+1}{j} 3^{j/2} \\ (1 - \sqrt3)^{2n+1} &= \sum_{j=0}^{2n+1} \binom{2n+1}{j} (-1)^j 3^{j/2} \\ (1 + \sqrt3)^{2n+1} + (1 - \sqrt3)^{2n+1} &= \sum_{j=0}^{2n+1} \binom{2n+1}{j} (1 + (-1)^j) 3^{j/2} \\ &= 2 \sum_{k=0}^n \binom{2n+1}{2k} 3^k \end{align} because $(1 + (-1)^j)$ becomes $0$ for odd $j$ and $2$ for even $j$.

---

Once we have the formula with square roots, we can get a recurrence relation by observing that $1 \pm \sqrt3$ are the roots of $x^2 - 2x - 2 = 0$, so they satisfy $x^2 = 2x+2$ and $x^{n+1} = 2(x^n + x^{n-1})$.

As a result, if $a_n$ is any linear combination of $(1+\sqrt3)^n$ and $(1-\sqrt3)^n$, it also satisfies $a_{n+1} = 2(a_n + a_{n-1})$, and the factor of $2$ in this recurrence accumulates to give us the power of $2^n$ we want. There are a number of ways to turn this into a proof by induction.

Answer 5

We show the following binomial identity for integral $n\geq 0$ is valid: \begin{align*} \sum_{k=0}^n\binom{2n+1}{k}3^k=\color{blue}{2^n}\left(\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n}{2k}3^k2^{n-2k} +\sum_{k=0}^{\lfloor n/2 \rfloor-1}\binom{n}{2k+1}3^{k+1}2^{n-(2k+1)}\right)\tag{1} \end{align*} We have a factor $\color{blue}{2^n}$ at the right-hand side of (1). Since the sums in parentheses are non-negative integers the claim follows immediately.

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\binom{2n+1}{2k}3^k}\\ &=\sum_{k=0}^{2n+1}\binom{2n+1}{k}(\sqrt{3})^k\frac{1+(-1)^k}{2}\\ &=\frac{1}{2}\sum_{k=0}^{2n+1}\binom{2n+1}{k}(\sqrt{3})^k+\frac{1}{2}\sum_{k=0}^{2n+1}\binom{2n+1}{k}(-\sqrt{3})^k\\ &=\frac{1}{2}\left(1+\sqrt{3}\right)^{2n+1}+\frac{1}{2}\left(1-\sqrt{3}\right)^{2n+1}\\ &=\frac{1}{2}\left(1+\sqrt{3}\right)\left(4+2\sqrt{3}\right)^{n}+\frac{1}{2}\left(1-\sqrt{3}\right)\left(4-2\sqrt{3}\right)^{n}\\ &=2^{n-1}\left(1+\sqrt{3}\right)\sum_{k=0}^n\binom{n}{k}(\sqrt{3})^k2^{n-k} +2^{n-1}\left(1-\sqrt{3}\right)\sum_{k=0}^n\binom{n}{k}(-\sqrt{3})^k2^{n-k}\\ &=2^{n}\sum_{k=0}^n\binom{n}{k}(\sqrt{3})^k2^{n-k}\frac{1+(-1)^k}{2} +2^{n}\sqrt{3}\sum_{k=0}^n\binom{n}{k}(-\sqrt{3})^k2^{n-k}\frac{1-(-1)^k}{2}\\ &=2^{n}\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n}{2k}3^k2^{n-2k} +2^{n}\sum_{k=0}^{\lfloor n/2 \rfloor -1}\binom{n}{2k+1}3^{k+1}2^{n-(2k+1)}\\ &\,\,\color{blue}{=2^n\left(\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n}{2k}3^k2^{n-2k} +\sum_{k=0}^{\lfloor n/2 \rfloor-1}\binom{n}{2k+1}3^{k+1}2^{n-(2k+1)}\right)} \end{align*} and the claim (1) follows.