The following is an Olympiad Competition question, so I expect it to have a pretty solution:

For a positive integer $d$, define the sequence: \begin{align} a_0 &= 1\\ a_n &= \begin{cases} \frac{a_{n-1}}{2}&\quad\text{if }a_{n-1}\text{ is even}, \\ a_{n-1}+d &\quad\text{if }a_{n-1}\text{ is odd.} \end{cases} \end{align} Find all values of $d$ such that $a_n=1$ for some $n>0$.

It is obvious that $d$ must be odd, or else the sequence is monotone increasing. Also, I have numerically observed that all odd values of $d$ seem to work. Can anyone provide a hint as to how to even begin to prove this? Thank you!

-
Did you intend "... if $a_n$ is even, .... if $n$ is odd." Should $n$, or $a_n$ be used in both predicates? –  Sasha Aug 16 '12 at 16:05
Thanks for pointing that out. I edited the question –  Raj Raina Aug 16 '12 at 16:25
Yes I have tried induction, but I see no way of relating previous values of $d$ with bigger values of $d$ (i.e. the induction step) –  Raj Raina Aug 16 '12 at 16:40
@RajRaina There still seems be to a typo. Did you mean to say $a_{n+1} = \frac{a_n}{2}$ if $a_n$ is even, and $a_{n+1} = a_n + d$ if $a_n$ is odd? –  Sasha Aug 16 '12 at 16:41
AHH sorry for not proofreading more carefully! I edited :) –  Raj Raina Aug 16 '12 at 16:43

Here is an outline of an argument. Our guess was that the sequence goes back to $1$ for any $d = 2m-1$.

First, it seems preferable to work with the sequence

$$b_0 = 1, \quad b_n = \begin{cases} \dfrac{b_{n-1}}2 & (b_{n-1}\text{ even}) \\ \frac{b_{n-1}+d}2 & (b_{n-1} \text{ odd})\end{cases}$$

instead of $a_n$ (the statement to be proven remains the same).

Hint: Show that it is enough to show $b_n\equiv 1 \pmod d$ for some $n$. What does the sequence $b_n$ look like mod $d$?

I have included a more detailed outline below (but I fear it is giving away way too much!)

Claim 1: We have $0<b_n<d$ for all $n$.

-

This allows us to work mod $d$ from now on, i.e. we have $b_n = 1$ if and only if $b_n\equiv 1 \pmod d$.

-

Claim 2: $\frac12 \equiv m \pmod d$, where $d=2m-1$ as above.

-

Now notice that the sequence is really simple when considered $\pmod d$! Use this to show

-

Claim 3: $b_n \equiv m^n \pmod d$

-

Claim 3 implies that $b_k \equiv 1 \pmod d$ for some $k$ (why?), so by Claim 1 it follows that $b_k=1$ for this $k$. $\square$

-
Since you tagged the question (homework) I assume you wanted a hint rather than a full solution. Please let me know whether you think the above format is helpful in this/how it could be improved... –  Sam Aug 16 '12 at 17:59
A nice argument. You actually show what the return time is, not just that it does return as I do. –  Ross Millikan Aug 16 '12 at 18:09
@RossMillikan: Thank you. Yes, at least for the $b_n$, the return time is given by $\mathrm{ord}(m)$, where $m\in \mathbb Z_{2m-1}^\times$ and $d = 2m-1$. But it doesn't seem easy to get a return time for the $a_n$ from this (although it does give an upper bound of $2\varphi(d)$). –  Sam Aug 16 '12 at 18:20
@SamL. I posed a related question before seeing your response. Your response answers the question completely though. You might want to respond to it, to claim the credit. Thanks! –  Sasha Aug 16 '12 at 18:59
Thank you Sam L. If I am understanding correctly, we can now say that $b_{n}\equiv 2^{−n}\pmod d$ (Claim 3), and so we need $2^n \equiv 1 \pmod d$, which has the trivial solution $n = \phi (d)-1$ since $2$ and $d$ are relatively prime, and so we will always have $b_{\phi(d)-1} =1$. What a simple solution! But what was Claim 2 necessary for? –  Raj Raina Aug 16 '12 at 23:12

It is true that you return to $1$ for all odd $d$, and the power of $2$ that you get to for the return is the next power of $2$ above $d$.

All odd numbers in the series are less than $d$, which means it must cycle. If $a_n$ is odd and less than $d$, $a_{n+1}$ is less than $2d$ and even, so the next odd is again less than $d$.

To have a cycle that does not include $1$ you must have a number that can be reached from two different numbers-one to enter the cycle and one to continue it. But this is impossible-odd numbers have to be reached by division by $2$, even numbers greater than $d$ have to be reached by addition, and even numbers less than $d$ have to be reached by division.

-
Thank you for your help! –  Raj Raina Aug 16 '12 at 23:04

The question has already an "accepted" answer - but the following scheme may be useful for some later reader anyway.
The iterative dividing and adding can be expressed as a whole operation.
We formulate one transformation as $$a_{k+1}={a_k+d \over 2^A }$$ and work on odd $a_k$ only. The value for A is determined by the requirement, that it is the highest A such that the result of the transformation is an odd integer.
The second transformation is then $$a_{k+2}={{a_k+d \over 2^A }+d \over 2^B} = {a_k \over 2^{A+B} } + d \cdot ({1 \over 2^{A+B} } + {1 \over 2^B} )$$ and so on.

Let the h subsequent exponents of such transformations $a_0 \to a_h = 1$ be denoted as $A,B,C,\ldots,G,H$ and their sum as $S$. Then the full transformation can be written as
$$1 (=a_h) = {a_0 \over 2^S} + d \cdot {(1+2^A + 2^{A+B} + \ldots + 2^{A+B+\ldots + G})\over 2^S}$$ and we must have an integer solution for
$$2^S = a_0 + d \cdot (1+2^A + 2^{A+B} + \ldots + 2^{A+B+\ldots +G})= a_0 + d \cdot x$$
where S is to be found (if there is a solution in $A,B,C,\ldots,H$ at all!).

Thus we solve for S such that $2^S = a_0 \pmod d$ which must in general be done by searching (see "discrete-logarithm-problem").
Now here seems to be the critical problem of the original question: we need to know such combinations of $d$ and $a_0$ that this equation has a solution at all. Possibly this is also meant to be the core problem in your homework-assignment, so I won't proceed here ( #1 see below)

If in fact there is a solution for some S then we compute
$$x = { 2^S - a_0 \over d}$$. Then the bits in the binary representation of x correspond to the "division by 2's" of the original formulation of the problem.

For instance, with $a_0 = 605, d=13$ I found $2^S = a_0 + d \cdot x$ with $S=11, x=111$ and $2048 = 605 + 13 \cdot 111$

(#1): Referring to another answer we might reformulate this as $2 = a_0^{1 \over S} \pmod d$ which hints to the concept of "primitive roots (mod p)".

-