# Homework Help: Binomial theorem and modular arithmetic

1. Aug 28, 2014

1. The problem statement, all variables and given/known data
From an old exam: Show that
\begin{equation*}
\sum_{0 \leq 2k \leq n} \binom{n}{2k}2^k = 0 (3) \text{ iff } n = 2 (4).
\end{equation*}
By $a = b (k)$ I mean that $a$ is congruent to $b$ modulo $k$.

2. Relevant equations
Binomial theorem: $(a + b)^m = \sum_{k=1}^m \binom{k}{m} a^k b^{m-k}$.

3. The attempt at a solution
A hint was provided to consider $\frac{1}{2}((1 + \sqrt{2})^n + (1 - \sqrt{2})^n)$.

I have taken some baby steps. Using the binomial theorem, I was able to establish
\begin{equation*}
\sum_{0 \leq 2k \leq n} \binom{n}{2k}2^k = \frac{1}{2}((1 + \sqrt{2})^n + (1 - \sqrt{2})^n).
\end{equation*}
Now in other words I need to find for exactly which $n$ the above is divisible by $3$, which I guess is equivalent to saying that $((1 + \sqrt{2})^n + (1 - \sqrt{2})^n)$ is divisible by $6$.

I would greatly appreciate some small hints.

2. Aug 28, 2014

### pasmith

Given that $a_n = A\lambda_1^n + B\lambda_2^n$ is the general solution of the linear recurrence relation $$a_{n+2} - (\lambda_1 + \lambda_2)a_{n+1} + \lambda_1\lambda_2a_n = 0,$$ I am motivated to view $\frac12((1 + \sqrt{2})^n + (1 - \sqrt{2})^n)$ as being the solution of that recurrence relation with $\lambda_{1} = 1 + \sqrt{2}$, $\lambda_2 = 1 - \sqrt{2}$ and initial conditions $a_0 = a_1 = 1$, and consider $b_n = a_n \mod 3$. I suspect you will find that $b_n$ is periodic with period equal to some multiple of 4.

3. Aug 28, 2014

Indeed, by considering $b_n = a_n (3)$ I use the recurrence relation to find that $b_n$ is periodic and $b_n = 0 (3)$ exactly when $n = 2 + 4m$.