Discrete mathematics. Just an impression, or this is always true?

Question

I feel that the following is always true:

$$ \frac{2^k-1}{3} \equiv 1 ~(\text{mod }2) \text{ if }k \equiv 0 ~(\text{mod }2) \wedge k \geq 2$$

I've just tried it using a "brute force" approach, but I'm not able to prove it in a formal way. Where can I start?

Answer 1

$$ \frac{2^k-1}{3} \equiv 1 ~(\text{mod }2) \hspace{10mm}\Leftrightarrow\hspace{10mm} 2^k-1 \equiv 3 \equiv 1~(\text{mod }2) \hspace{10mm}\Leftrightarrow\hspace{10mm} 2^k \equiv 0 ~(\text{mod }2). $$ The last claim is certainly true. By the way, it is true for all $k\ge 1$.

Answer 2

$$\frac{2^k-1}3=\frac{0-1}1\pmod 2=-1=1\pmod2$$

Answer 3

When k is even, $$ 2^k = 2^{2n} = 4^n $$

Factoring (when n > 0):

$$ 4^n - 1 = (4-1) \times (1 + 4 + ... + 4^{n-1}) = 3 \times (1 + 4x) $$ (for some integer x), which gives us: $$ {{2^k-1}\over 3} = {{(4^n -1)}\over{3}} = 1 + 4x = 1\mod 2 $$

When k is odd, k = (2n+1)

$$ 2^k - 1 = 2^{2 n + 1} - 1 = 4^n\times 2 - 1 = 4^n + 4^n - 1 = 4^n + 3\times(1+4x) $$ and $$ {{2^k-1}\over 3} = {{4^n + 3\times(1+4x)}\over 3} = {{4^n}\over 3} + (1+4x) $$

Since $$ 4^n \neq 0 \mod 3, $$ this is never an integer, so $$ {{2^k-1}\over 3} \neq 1\mod 2 $$