Prove that for any positive integer $n$ the number $1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$ is divisible by $2^{n-1}$.

Question

Let $a=4k-1$, where $k \in \mathbb{Z}$. Prove that for any positive integer $n$ the number

$$1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$$

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

My attempt: Note that if $k>n$, then ${n \choose k}=0$ (I assume that this is true, but I am not sure about this). Then by the Binomial theorem, the number can be written as

$$(1-a)^n=(2-4k)^n=2^n(1-2k)^n$$

Clearly $2^n(1-2k)^n$ is divisible by $2^{n-1}$.

This question is taken from the book Putnam and Beyond, question $308$, page $104$.

Answer 1

$$A_n = 1-\binom{n}{2}a+\binom{n}{4}a^2-\ldots = \frac{1}{2}\left[(1+i\sqrt{a})^n + (1-i\sqrt{a})^n\right].$$ Provided that:

$$ A_{n+2} = 2 A_{n+1} - (a+1) A_n $$ the claim easily follows by induction.