Proof with induction on a sequence

Question

Let $\{a_k\}_{k=0}^\infty$ be a sequence where

$a_0 = 0$

$a_1 = 0$

$a_2 = 2$

$\forall k \geq 3, a_k = a_{\lfloor k/2 \rfloor} + 2$

Show that every element of this sequence is even.

I am stuck on the induction step, and can't seem to prove that $a_n$ is even $\implies a_(n+1)$ is even . Could someone please give me some hints.

Answer 1

If $k$ is written in binary, deleting the rightmost digit of $k$ obtains $\big\lfloor\tfrac{k}{2}\big\rfloor$, but we are told $a_k$ has the same parity as $a_{\big\lfloor\tfrac{k}{2}\big\rfloor}$. Induction on the number of binary digits of $k$ completes the proof.