I've got a (hard?) Putnam-style problem that I've been given to look at . . . I've never worked any problem even vaguely like this, but my director thinks I should be able to do it. I doubt it (100% not my area or my taste in problem), so I need some help!
The problem posed is to prove that 5 does not divide $\sum_{k=0}^{n} {{2n+1} \choose {2k+1}}2^{3k}$ for any $n$.
I can interpret the summation well enough from a design or lattice path perspective, but a bijection-type proof seems futile. I've played around with some binomial identities trying to clean the expression up, but I don't have any real experience with that sort of thing and nothing seemed to "simplify" the problem.
So, I'm just wondering if anyone has a nice proof, preferably without using generating functions - alternatively, what are the basic techniques typically used in this sort of problem, if there is any such thing? There seem to be a lot of ways to approach the problem, but not having any experience with this I don't know what direction to go, nor do I have background in most of those apparent directions =P
Thanks a lot!
Work inside the finite field $K=\Bbb{F}_{25}$. Let $\alpha=\sqrt3=\sqrt8\in K$. Then $\alpha^2=2^3$ and $K=\Bbb{F}_5[\alpha]$.
Your sum (projected into $K$) is $$ A=\sum_{k=0}^n\binom{2n+1}{2k+1}\alpha^{2k}. $$ Let us denote by $$ B=\sum_{k=0}^n\binom{2n+1}{2k}\alpha^{2k}. $$
By binomial formula we have $$ B+\alpha A=(1+\alpha)^{2n+1}, $$ and $$ B-\alpha A=(1-\alpha)^{2n+1}, $$ implying $$ A=\frac1{2\alpha}\left[(1+\alpha)^{2n+1}-(1-\alpha)^{2n+1}\right].\qquad(*) $$ The claim is equivalent to $A\neq 0_K$ for all $n$. We see that $A=0$ if and only if $$ (1+\alpha)^{2n+1}=(1-\alpha)^{2n+1}. $$ Hence the claim fails, iff $$ \left(\frac{1+\alpha}{1-\alpha}\right)^\ell=1_K\qquad(**) $$ for some odd integer $\ell$.
The multiplicative group of $K$ is cyclic of order $24=2^3\cdot3$. Thus any element is either a cubic root of unity, or it is of an even order. Thus equation $(**)$ is impossible, unless $$ \left(\frac{1+\alpha}{1-\alpha}\right)^3=1_K. $$ There are many ways of showing that this cannot be the case - your pick. Unless I made a mistake that cube evaluates to $-1$. Just as well, because the sixth power of that ratio would be equal to the norm of the ratio of conjugates, and thus equal to $1_K$.
In retrospect the formula $(*)$ seems to imply that the residue class of $A$ modulo $5$ is periodic (as a function of $n$) of period $d\mid 12$.