Proving divisibility of a sum $\sum_{k=0}^{\lfloor{n/2}\rfloor} (-1)^{k}\binom{n}{2k} 7^{k}$

Question

I have been given $$ \sum_{k=0}^{\lfloor{n/2}\rfloor} (-1)^{k}\binom{n}{2k} 7^{k} $$. How can I show that it is divisible by $2^{n - 1}$ for any positive integer $n$? I have attempted to write it in terms $$ \sum_{k=0}^{n} i^{k}\binom{n}{k} \frac{1+(-1)^k}{2}7^{k} = ... = \frac{1}{2}[(1+7i)^n + (1-7i)^n] $$ but I am stuck. I think there might be some recursion pattern but I am not sure. Any hints?

EDIT:

I have rewritten the above expression using complex numbers, so the 2nd expression is now equal to the first

Answer 1

We can write the sum in closed form as \begin{align*} \color{blue}{\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^k\binom{n}{2k}7^k} &=\sum_{k=0}^n\binom{n}{k}\left(i\sqrt{7}\right)^k\frac{1+(-1)^k}{2}\\ &\color{blue}{=\frac{1}{2}(1+i\sqrt{7})^n+\frac{1}{2}(1-i\sqrt{7})^n} \end{align*} We want to show that for $n\geq 1$ \begin{align*} 2^{n-1} \Bigg| \left(\frac{1}{2}(1+i\sqrt{7})^n+\frac{1}{2}(1-i\sqrt{7})^n\right) \end{align*}

We show equivalently for $n\geq 1$ \begin{align*} \color{blue}{a_n:=\frac{1}{2^n}(1+i\sqrt{7})^n+\frac{1}{2^n}(1-i\sqrt{7})^n\in\mathbb{Z}}\tag{1} \end{align*} We give a proof by induction on $n$.

Base step:

We obtain for $n=1$ and $n=2$: \begin{align*} \color{blue}{a_1}&=\frac{1}{2}(1+i\sqrt{7})+\frac{1}{2}(1-i\sqrt{7})\color{blue}{=1\in\mathbb{Z}}\\ \color{blue}{a_2}&=\frac{1}{2^2}(1+i\sqrt{7})^2+\frac{1}{2^2}(1-i\sqrt{7})^2\\ &=\frac{1}{4}\left(1+2i\sqrt{7}-7\right)+\frac{1}{4}\left(1-2i\sqrt{7}-7\right)\\ &\color{blue}{=-3\in\mathbb{Z}} \end{align*}

Induction hypothesis: $n=N$

We assume the validity of \begin{align*} \color{blue}{a_N}=\frac{1}{2^N}(1+i\sqrt{7})^N+\frac{1}{2^N}(1-i\sqrt{7})^N\color{blue}{\in\mathbb{Z}} \end{align*}

Induction step: $n=N+1$ \begin{align*} \color{blue}{a_{N+1}}&=\frac{1}{2^{N+1}}(1+i\sqrt{7})^{N+1}+\frac{1}{2^{N+1}}(1-i\sqrt{7})^{N+1}\\ &=\frac{1}{2^{N-1}}(1+i\sqrt{7})^{N-1}\frac{1}{4}(1+i\sqrt{7})^2 +\frac{1}{2^{N-1}}(1-i\sqrt{7})^{N-1}\frac{1}{4}(1-i\sqrt{7})^2\\ &=\frac{1}{2^{N-1}}(1+i\sqrt{7})^{N-1}\frac{1}{4}(-6+2i\sqrt{7}) +\frac{1}{2^{N-1}}(1-i\sqrt{7})^{N-1}\frac{1}{4}(-6-2i\sqrt{7})\\ &=\frac{1}{2^{N-1}}(1+i\sqrt{7})^{N-1}\frac{1}{2}(-3+i\sqrt{7}) +\frac{1}{2^{N-1}}(1-i\sqrt{7})^{N-1}\frac{1}{2}(-3-i\sqrt{7})\\ &=\frac{1}{2^{N-1}}(1+i\sqrt{7})^{N-1}\left(\frac{1}{2}(1+i\sqrt{7})-2\right)\\ &\qquad+\frac{1}{2^{N-1}}(1-i\sqrt{7})^{N-1}\left(\frac{1}{2}(1-i\sqrt{7})-2\right)\\ &\color{blue}{=a_{N}-2a_{N-1}\in\mathbb{Z}} \end{align*} and the claim (1) follows.

Answer 2

Hint: try to use the identity $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$. If you apply this in your sum, you'll get $\binom{n}{2k} = \binom{n-1}{2k} + \binom{n-1}{2k-1}$. Its enough, because it contains all coefficient's denominators: even and odd. And I would put also together $(-1)^k \cdot 7^k$ to get $(-7)^k$

Answer 3

Let $\alpha=\frac{1}{2}(1+ \sqrt{-7})$ and $\beta=\frac{1}{2}(1-\sqrt{-7})$.

Note that $\alpha$ and $\beta$ are algebraic integers. (Consider $x^2-x+2\in \mathbb{Q}[x]$)

So $\alpha^n$ and $\beta^n$ are also algebraic integers.

Thus $\alpha^n+\beta^n$ is algebraic integer.

Since $\alpha^n+\beta^n\in \mathbb{Q}$ and $\alpha^n+\beta^n$ is algebraic integer, $\alpha^n+\beta^n$ is integer.

Therefore your expression is divisible by $2^{n-1}$.