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.

  • $\endgroup$
    • $\begingroup$ even+even=even. $\endgroup$
      – John B
      Commented Mar 8, 2016 at 23:34
    • $\begingroup$ Instead of $P(n) \implies P(n+1)$ you can use $(\forall 0\le k \le n, P(k)) \implies P(n+1)$ $\endgroup$ Commented Mar 12, 2016 at 16:56

    1 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.


    You must log in to answer this question.

    Not the answer you're looking for? Browse other questions tagged .