# Find the value of a_{1000}.

#### anemone

##### MHB POTW Director
Staff member
Hi members of the forum,

I am unable to determine the value of $$\displaystyle a_{1000}$$ in the problem as stated below because I think I failed to observe another useful pattern of the given sequence.

Problem:
A sequence $$\displaystyle a_1$$, $$\displaystyle a_2$$, $$\displaystyle a_3,\;\cdots$$ of positive integers satisfies the following properties:

$$\displaystyle a_1=1$$

$$\displaystyle a_{3n+1}=2a_n+1$$

$$\displaystyle a_{n+1}\ge a_n$$

$$\displaystyle a_{2001}=200$$

Find the value of $$\displaystyle a_{1000}$$

#### chisigma

##### Well-known member
Hi members of the forum,

I am unable to determine the value of $$\displaystyle a_{1000}$$ in the problem as stated below because I think I failed to observe another useful pattern of the given sequence.

Problem:
A sequence $$\displaystyle a_1$$, $$\displaystyle a_2$$, $$\displaystyle a_3,\;\cdots$$ of positive integers satisfies the following properties:

$$\displaystyle a_1=1$$

$$\displaystyle a_{3n+1}=2a_n+1$$

$$\displaystyle a_{n+1}\ge a_n$$

$$\displaystyle a_{2001}=200$$

Find the value of $$\displaystyle a_{1000}$$
The subsequence obeys to the difference equation...

$\displaystyle a_{k+1} = 2\ a_{k}+1,\ a_{1}=1$ (1)

... the solution of which is...

$\displaystyle a_{i}= 2^{k}-1$ (2)

... and the index obeys to the difference equation...

$i_{k+1}= 3\ i_{k}+1,\ i_{1}=1$ (3)

... the solution of which is...

$i_{k} = \frac{1}{2} (3^{k}-1)$ (4)

Now we plot the sequence $a_{i}$ ...

$\displaystyle a_{1}=1,\ a_{4}= 3,\ a_{13}= 7,\ a_{40}= 15,\ a_{121}= 31,\ a_{364} = 63,\ a_{1093}= 127,\ ...$ (5)

Now, observing (5), all what we can say about $a_{1000}$ is [for the moment...] $63 \le a_{1000} \le 127$ ...

Kind regards

$\chi$ $\sigma$

Last edited:

#### anemone

##### MHB POTW Director
Staff member
The subsequence obeys to the difference equation...

$\displaystyle a_{k+1} = 2\ a_{k}+1,\ a_{1}=1$ (1)

... the solution of which is...

$\displaystyle a_{i}= 2^{k}-1$ (2)

... and the index obeys to the difference equation...

$i_{k+1}= 3\ i_{k}+1,\ i_{1}=1$ (3)

... the solution of which is...

$i_{k} = \frac{1}{2} (3^{k}-1)$ (4)

Now we plot the sequence $a_{i}$ ...

$\displaystyle a_{1}=1,\ a_{4}= 3,\ a_{13}= 7,\ a_{40}= 15,\ a_{121}= 31,\ a_{364} = 63,\ a_{1093}= 127,\ ...$ (5)

Now, observing (5), all what we can say about $a_{1000}$ is [for the moment...] $63 \le a_{1000} \le 127$ ...

Kind regards

$\chi$ $\sigma$
Hi chisigma, thank you so much for replying to this problem. But do you mean to say we could in the next step to determine what the integer value of $$\displaystyle a_{1000} is$$? #### Opalg

##### MHB Oldtimer
Staff member
Given that $a_{2001} = 200$, it follows that $a_{2002}\geqslant 200$. But $2002 = 3*667 + 1$, so $a_{2002} = 2a_{667}+1$. Therefore $2a_{667}+1\geqslant 200$, and $a_{667}\geqslant \frac12(199) = 99.5.$ But $a_{667}$ is an integer, and so $a_{667}\geqslant 100$. Repeating that chain of deductions, you see that $a_{223} \geqslant 50$, $a_{74} \geqslant 25$, $a_{25}\geqslant 12$, $a_8\geqslant7.$ But $a_{13}=7$ (see chisigma's post above), and so $a_8\leqslant7.$ Thus $a_8=7$, and in fact $a_n=7$ for each $n$ between $8$ and $13$ inclusive.

Next, $3*8+1=25$, so $a_{25} = 2a_8+1 = 15$, and in fact $a_n=15$ for each $n$ between $25$ and $40$ inclusive. Continue in that way to see that $a_n=31$ for each $n$ between $76$ and $121$, $a_n=63$ for each $n$ between $229$ and $364$, $a_n=127$ for each $n$ between $668$ and $1093$. In particular, $a_{1000} = 127.$

#### chisigma

##### Well-known member
Hi chisigma, thank you so much for replying to this problem. But do you mean to say we could in the next step to determine what the integer value of $$\displaystyle a_{1000} is$$? We can extrapolate the result writing...

$\displaystyle \ln (y+1) \sim \ln 2x \frac{\ln 2}{\ln 3} \sim .6309 \ln 2x$ (1)

$a_{31} \sim 30.9$

$a_{364} \sim 62.9$

$a_{1093} \sim 126,9$

... so that we could conclude that...

$a_{1000} \sim 119.9$

Unfortunately the 'extra information' $a_{2001}= 200$ is not coherent with (1) because it should be $a_{2001} \sim 186.4$ ...

Kind regards

$\chi$ $\sigma$