<s>[INST] Equivalent condition for the divisibility by $2^{n-1}$. I guess that the equivalent condition that for any positive integer $n,m$
$$ \sum_{k \ge 0} \binom {n}{2k} m^k $$ is divisible by $2^{n-1}$ is that
$$m \equiv 1(mod 4).$$ Would you explain the reason why?
 [/INST] $$ \sum_{k \ge 0} \binom {n}{2k} m^k =\sum_{k \ge 0} \binom {n}{2k} m^k 1^{n-2k}$$
$$=\frac{1}{2} [ \sum_{k \ge 0} \binom {n}{k} ( \sqrt{m})^k 1^{n-k} +  \sum_{k \ge 0} \binom {n}{k} ( - \sqrt{m})^k 1^{n-k} ]
\\=\frac{1}{2} [ (1+ \sqrt m)^n + (1- \sqrt m )^n ]. $$ 
Note that if we let $r:=x+y, s:=xy$ and let $f_n (r,s):= \frac{x^n +y^n}{2}$
then $$ f_{n+1} (r,s)=rf_n(r,s)+sf_{n-1}(r,s)   (n \ge 0).$$ 
$f_0 (r,s)= 1, f_1 (r,s)=r/2.$ Note also that $f_2(r,s)=(x^2+y^2)/2 =[(x+y)^2 -2xy]/2=(r^2-2s)/2.$
Now $x=1+ \sqrt{m}, y=1- \sqrt{m}$ then $r=2, s=1-m$ which is a multiple of 4 since $ m \equiv 1(mod 4)$. By induction on $n$ the claim follows.
</s>