Problem involving summation and binomial coefficient

Question

I have been fighting with this but I'm really not getting anywhere. $$\sum_{0\leq2k\leq n}\binom{n}{2k}2^k\equiv0\pmod 3$$ $$iff$$ $$n\equiv2\pmod 4$$ Hint: Consider $$\frac{1}{2}((1+\sqrt{2})^n+(1-\sqrt{2})^n)$$ Help would be appreciated. Thanks!

Answer 1

If you expand the last expression with the binomial theorem you will see that it matches with the first one. The next step is to prove that the sequence defined by $$ a_n = \frac{1}{2}\left((1+\sqrt{2})^n+(1-\sqrt{2})^n\right)$$ satisfies the recurrence relation:

$$ a_{n+2} = 2 a_{n+1} + a_{n},\quad a_0 = 1,a_1=1 $$ hence the sequence $\!\!\pmod{3}$ is $\overline{1,1,0,1,2,2,0,2}$ and the zeroes occur iff $n\equiv 2\pmod{4}$.

Answer 2

Another trick to show this is the following:

$2^k = (-1)^k$ mod $3$.

So you are left with the alternating sum $n \choose 0$- $n \choose2$+ $n \choose 4$-... (mod $3$).

You can now easily see that if $n = 2$ (mod $4$ )then this sum is zero.