The sequence $(a_n)$ is given as $a_1=1, a_{2n} = a_n - 1, a_{2n+1} = a_n + 1$. $a_{2015}=$?

Question

The sequence $(a_n)$ is given as $a_1=1, a_{2n} = a_n - 1, a_{2n+1} = a_n + 1$. What's the value of $a_{2015}$

Correct answer should be $a_{2015} = 9$. How?

thing that came to mind was to see what $a_{2015}$ is composed of. So $a_{2015} = a_{(2*1007 + 1)} = a_{1007} + 1$ because $a_{2n+1} = a_n + 1$ and than to work that way down?

My teacher said that I am complicating too much, and I agree, but what am I missing to solve this?

Answer 1

Think about the procedure that you had in mind. If the binary representation of $n$ ends in $1$, then $n$ is odd; say $n=2k+1$. Then $a_n=a_k+1$, and the binary representation of $k$ is simply what’s left when you drop the last digit of $n$. If the binary representation of $n$ ends in $0$, then $n$ is even; say $n=2k$. Then $a_n=a_k-1$, and again the binary representation of $k$ is simply what’s left when you drop the last digit of $n$. Thus, you’ll add $1$ for every $1$ in the binary representation of $n$, and you’ll subtract $1$ for every $0$.

Write $2015$ in binary: it’s $11111011111$, which has $10$ ones and $1$ zero, so the process will result in $10$ additions of $1$ and one subtraction, for a total of $9$. (You do have to check that setting $a_1=1$ is consistent with this scheme.)

This is the shortcut that your teacher had in mind.

Answer 2

Actually, you made a mistake breaking down $a_{2015}$. It should be $a_{2015}=a_{2\times 1007+1}=a_{1007}+1$.

And $a_{1007}=a_{2\times503+1}=a_{503}+1$

$a_{503}=a_{2\times 251+1}=a_{251}+1$

$a_{251}=a_{2\times 125+1}=a_{125}+1$

$a_{125}=a_{2\times 62+1}=a_{62}+1$

$a_{62}=a_{2\times 31+1}=a_{31}-1$

$a_{31}=a_{2\times 15+1}=a_{15}+1$

$a_{15}=a_{2\times 7+1}=a_{7}+1$

$a_{7}=a_{2\times 3+1}=a_{3}+1$

$a_{3}=a_{2\times 1+1}=a_{1}+1$

So, $a_{2015}=a_{1}+1+1+1+1+1+1+1+1+1-1=9$