Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
show 1 more comment

3 Answers

up vote 6 down vote accepted

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$

share|improve this answer
    
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
show 1 more comment

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.

share|improve this answer
    
Thank you for your help! –  Raj Raina Aug 16 '12 at 23:04
add comment

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)".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.