Peter wrote: Prove that the number \[\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}\] is not divisible by $5$ for any integer $n\geq 0$. [Observation] We evaluate the the combinatorial sum \[B_{n}= \sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}\] by finding a non-cominatorial expression. By Binomial Theorem, setting \[P_{n}= \sum_{0 \leq i \leq 2n+1, \; i \tex{: \;odd}}\binom{2n+1}{i}\left( 2^{\frac{3}{2}}\right)^{i}\;\; \text{and}\;\; G_{n}= \sum_{0 \leq k \leq 2n+1, \; i \tex{: \;even}}\binom{2n+1}{i}\left( 2^{\frac{3}{2}}\right)^{i},\] we obtain \[\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}= P_{n}+G_{n}= 2^{\frac{3}{2}}B_{n}+G_{n}\] and \[\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}=P_{n}-G_{n}=2^{\frac{3}{2}}B_{n}-G_{n}.\] Adding these two identities and multiplying $2^{-\frac{5}{2}}$, we obtain \[B_{n}= 2^{-\frac{5}{2}}\left(\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}+\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}\right).\] The right hand side is the desired non-combinatorial expression. [Solution] Our aim is to show that $B_{n}$ is not congruent to $0$ modulo $5$. We need his 'integral' girl friend $G_{n}$. Multiplying the above two indentities, we obtain \[7^{2n+1}=\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}= 8{B_{n}}^{2}-{G_{n}}^{2}.\] Our next job is, of course, to read the above equation modulo $5$. Since $7^{2n+1}\equiv (7^{2})^{n}\cdot 7 \equiv (-1)^{n}\cdot 2 \; (mod \; 5)$, we obtain \[\pm 2 \equiv 8{B_{n}}^{2}-{G_{n}}^{2}\; (mod \; 5).\] From this, we see that $B_{n}\not\equiv 0 \; (mod \; 5)$. Indeed, $B_{n}\equiv 0 \;(mod \; 5)$ and the above congruence imply that \[\pm 2 \equiv-{G_{n}}^{2}(mod \; 5).\] However, this is a contradiction. Even Homer Simpson can check that $l^{2}\equiv-1, 0, 1 (mod \; 5)$ holds for all $l \in \mathbf{Z}$.

Suppose for the sake of contradiction that our sum is a multiple of 5 for some $ n$. Then it is 0 in the finite field $ F_{25}$. Considering our equation in $ F_{25}$, we have $ \sum_{k=0}^n \binom{2n+1}{2k+1} 8^k = 0$. $ 8 = 3$ in $ F_{25}$, so $ \sum_{k=0}^n \binom{2n + 1}{2k + 1} 3^k = 0$. Multiplying both sides by $ \sqrt{3}$, we get that $ \sum_{k=0}^n \binom{2n + 1}{2k + 1} (\sqrt{3})^{2k + 1}$. Let $ P(x) = (1 + x)^{2n + 1} = \sum_{k=0}^{2n+1} \binom{2n + 1}{k} x^k$. Then $ \frac{P(x) - P(-x)}{2} = \sum_{k=0}^n \binom{2n + 1}{2k + 1} x^{2k + 1}$. Thus, if $ \sum_{k=0}^n \binom{2n + 1}{2k + 1} (\sqrt{3})^{2k + 1}$, then $ \frac{P(\sqrt{3}) - P(-\sqrt{3})}{2} = 0$, that is, $ (1 + \sqrt{3})^n = (1 - \sqrt{3})^n$. Since $ 1 - \sqrt{3}$ is nonzero, we may multiply both sides by the inverse of $ (1 - \sqrt{3})^n$, to get $ (-2 - \sqrt{3})^n = 0$. But since $ -2 - \sqrt{3}$ is nonzero in $ F_{25}$, we arrive at a contradiction. I'm still a beginner with finite fields (and I think this is essentially the same as ideahitme's solution), so if anyone could verify this I'd appreciate it a lot.

My idea was to obtain a linear recursion formula, which is pretty straightforward: $ 2^{3k} = \frac{1}{\sqrt{8}}(\sqrt{8})^{2k + 1}$ Which implies the formula: $ \sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k} = \frac{1}{2\sqrt{8}}\left((1 + \sqrt{8})^{2n + 1} - (1 - \sqrt{8})^{2n+1}\right)$ Since $ 1 + \sqrt{8}$ and $ 1 - \sqrt{8}$ are the roots of the polynomial $ x^2 - 2x - 7$ we will need to consider the sequence $ a_n = 2a_{n-1} + 7a_{n-2}$, for which the above formula produces the odd terms. Computing shows $ a_0 = 0$ and $ a_1 = 1$. The sequence must obviously be periodic modulo 5, and straight computing shows that the sequence looks like this modulo 5: $ 0,1,2,1,4,0,3,1,3,3,2,0,4,3,4,4,1,0,2,4,2,2,3,0,1$ Since none of the odd terms are 0 the proof is finished.

first we need to define some terms: $a+b\sqrt{3} \equiv x \mod 5 \iff a \equiv x$ and $a+b\sqrt{3} \equiv x \mod 5_{\sqrt{3}} \iff b \equiv x$ where $a,b \in Z$ now let $p_n(x)=(1+x)^{2n+1} \implies \frac{p_n(x)-p_n(-x)}{2}=\sum_{k=0}^n \dbinom{2n+1}{2k+1} x^{2k+1}=x(\sum_{k=0}^n \dbinom{2n+1}{2k+1} x^{2k})$ which implies $\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k} \equiv \sum_{k=0}^{n}\binom{2n+1}{2k+1}3^{k} \mod 5$ $\sum_{k=0}^{n}\binom{2n+1}{2k+1}3^{k} = \frac{p_n(\sqrt{3})-p_n(-\sqrt{3})}{2\sqrt{3}}$ now it only takes to prove: $p_n(\sqrt{3})-p_n(-\sqrt{3}) \not\equiv 0 \mod 5_{\sqrt{3}}$ because $p_n(\sqrt{3})-p_n(-\sqrt{3})$ is in form of $n\sqrt{3}$ where $n \in N$ $p_n(\sqrt{3}) \equiv -p_n(-\sqrt{3}) \mod 5_{\sqrt{3}} \implies p_n(\sqrt{3})-p_n(-\sqrt{3})\equiv 0 \mod 5_{\sqrt{3}} \iff p_n(\sqrt{3}) \equiv 0 \mod 5_{\sqrt{3}}$ which is easy to prove $p_{2n+1}(\sqrt{3}) \equiv p_{2n+25}(\sqrt{3}) \mod 5_{\sqrt{3}}$ and because $p_{2n+1} \not\equiv 0 \mod 5_{\sqrt{3}}$ for $1\le 2n+1 \le 25$ which implies $\forall n: p_n(\sqrt{3}) \not\equiv 0 \mod 5_{\sqrt{3}}$

ideahitme wrote: Peter wrote: Prove that the number \[\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}\]is not divisible by $5$ for any integer $n\geq 0$. [Observation] We evaluate the the combinatorial sum \[B_{n}= \sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}\]by finding a non-combinatorial expression. By Binomial Theorem, setting \[P_{n}= \sum_{0 \leq i \leq 2n+1, \; i \text{:\;odd}}\binom{2n+1}{i}\left( 2^{\frac{3}{2}}\right)^{i}\;\; \text{and}\;\; G_{n}= \sum_{0 \leq i \leq 2n+1, \; i \text{:\;even}}\binom{2n+1}{i}\left( 2^{\frac{3}{2}}\right)^{i},\]we obtain \[\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}= P_{n}+G_{n}= 2^{\frac{3}{2}}B_{n}+G_{n}\]and \[\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}=P_{n}-G_{n}=2^{\frac{3}{2}}B_{n}-G_{n}.\]Adding these two identities and multiplying $2^{-\frac{5}{2}}$, we obtain \[B_{n}= 2^{-\frac{5}{2}}\left(\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}+\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}\right).\] The right hand side is the desired non-combinatorial expression. [Solution] Our aim is to show that $B_{n}$ is not congruent to $0$ modulo $5$. We need his 'integral' girl friend $G_{n}$. Multiplying the above two indentities, we obtain \[7^{2n+1}=\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}= 8{B_{n}}^{2}-{G_{n}}^{2}.\] Our next job is, of course, to read the above equation modulo $5$. Since $7^{2n+1}\equiv (7^{2})^{n}\cdot 7 \equiv (-1)^{n}\cdot 2 \; \pmod{5}$, we obtain \[\pm 2 \equiv 8{B_{n}}^{2}-{G_{n}}^{2}\; \pmod{5}.\] From this, we see that $B_{n}\not\equiv 0 \; \pmod{5}$. Indeed, $B_{n}\equiv 0 \;\pmod{5}$ and the above congruence imply that \[\pm 2 \equiv-{G_{n}}^{2}\pmod{5}.\]However, this is a contradiction. Even Homer Simpson can check that $l^{2}\equiv-1, 0, 1 \pmod{5}$ holds for all $l \in \mathbb{Z}$. BanziC wrote: My idea was to obtain a linear recursion formula, which is pretty straightforward: $ 2^{3k} = \frac{1}{\sqrt{8}}(\sqrt{8})^{2k + 1}$ Which implies the formula: $ \sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k} = \frac{1}{2\sqrt{8}}\left((1 + \sqrt{8})^{2n + 1} - (1 - \sqrt{8})^{2n+1}\right)$ Since $ 1 + \sqrt{8}$ and $ 1 - \sqrt{8}$ are the roots of the polynomial $ x^2 - 2x - 7$ we will need to consider the sequence $ a_n = 2a_{n-1} + 7a_{n-2}$, for which the above formula produces the odd terms. Computing shows $ a_0 = 0$ and $ a_1 = 1$. The sequence must obviously be periodic modulo 5, and straight computing shows that the sequence looks like this modulo 5: $ 0,1,2,1,$1$,4,0,3,1,3,3,2,0,4,3,4,4,1,0,2,4,2,2,3,0,1$ Since none of the odd terms are 0 the proof is finished.

Note that \begin{align*} \sum_{k=0}^n \binom{2n+1}{2k+1} 8^k & = \frac{1}{\sqrt{8}}\sum_{k=0}^n \binom{2n+1}{2k+1} \left (\sqrt{8}\right )^{2k+1} \\ & = \frac{1}{\sqrt{8}}\sum_{m=0}^{2n+1} \binom{2n+1}{m} \left (\sqrt{8}\right )^{m} \left(\frac{1-(-1)^m}2\right) \\ & = \frac{1}{2\sqrt 8} \sum_{m=0}^{2n+1} \binom{2n+1}k \left(\sqrt{8} \right)^m-\frac{1}{2\sqrt 8} \sum_{m=0}^{2n+1} \binom{2n+1}k \left(-\sqrt{8} \right)^m \\ & = \frac{1}{2\sqrt 8}\left(\left(\sqrt 8+1\right)^{2n+1}+\left(\sqrt 8-1\right)^{2n+1}\right) \end{align*}Now let us define the sequence $$a_n=\frac{1}{2\sqrt 8}\left(\left(\sqrt 8+1\right)^{2n+1}+\left(\sqrt 8-1\right)^{2n+1}\right)=\frac{\sqrt 8+1}{2\sqrt 8} \left(9+2\sqrt 8\right)^n+\frac{\sqrt 8-1}{2\sqrt 8} \left(9-2\sqrt 8\right)^n \qquad (1)$$for $n\geq 0$. The characteristic polynomial for this sequence is $x^2-18x+49=0$. So we get a recursion for our sequence, $$a_{n+2}=18a_{n+1}-49a_n \qquad (2)$$for all $n\geq 0$ and $a_0=1,a_1=11$ by $(1)$. Now we're ready to compute the values of $a_n$ modulo $5$. In mod $5$, we get the sequence $$1,1,4,3,3,2,4,4,1,2,2,3,1,1,4,\dots$$which is clearly periodic (with period $12$) due to $(2)$. In particular we notice that $a_n$ is never $0$ mod $5$ and this is what we wanted to prove.