1. ## Integers sequence

Show that the sequence of positive integers given by $\displaystyle a_{2n} = 3a_n -1, \ \ a_{2n+1}=3a_n +1$ is strictly increasing.
I have written down a reductio-ad-absurdum-proof, but it's based largely on tedious reduction of indices in $\displaystyle a$ and eventually showing that the argument is proved by the contradiction $\displaystyle 1\geq 2$, and now I'm not all that sure it is correct. Do you have any better ideas?

2. Hi

Maybe you can use an "explicit" form of $\displaystyle (a_n)$ showing by induction that,

given $\displaystyle a_0$

for every p integer

from $\displaystyle n=2^p$ to $\displaystyle 2^{p+1}-1$,

$\displaystyle a_n = 3^{p+1} a_0 + \alpha_n$ where $\displaystyle (\alpha_n)$ is a strictly increasing sequence of positive integers

3. Originally Posted by running-gag
Hi

Maybe you can use an "explicit" form of $\displaystyle (a_n)$ showing by induction that,

given $\displaystyle a_0$

for every p integer

from $\displaystyle n=2^p$ to $\displaystyle 2^{p+1}-1$,

$\displaystyle a_n = 3^{p+1} a_0 + \alpha_n$ where $\displaystyle (\alpha_n)$ is a strictly increasing sequence of positive integers
Hm... I'm not getting the induction thing at all... could you please explain it further?

4. Originally Posted by atreyyu
Hm... I'm not getting the induction thing at all... could you please explain it further?
If you calculate the first few terms of the sequence in terms of $\displaystyle a_1$, you get

(for n = 2 to 3)
$\displaystyle a_2 = 3a_1 - 1$
$\displaystyle a_3 = 3a_1 + 1$

(for n = 4 to 7)
$\displaystyle a_4 = 9a_1 - 4$
$\displaystyle a_5 = 9a_1 - 2$
$\displaystyle a_6 = 9a_1 + 2$
$\displaystyle a_7 = 9a_1 + 4$

and so on.

The idea is to show that the subsequence $\displaystyle a_p, ..., a_q$ where $\displaystyle p = 2^n$ and $\displaystyle q = 2^{n+1} - 1$ is strictly increasing, because each term of this subsequence can be written as $\displaystyle 3^na_1 + \alpha$, and the $\displaystyle \alpha$ are strictly increasing.

You also need to show that for each n, $\displaystyle a_x < a_y$, where $\displaystyle x = 2^n - 1$ and $\displaystyle y = 2^n$.

5. Ok, I decided to state that $\displaystyle a$ is composed of subsequences $\displaystyle c_k$, where $\displaystyle c_k=a_{2^k},a_{2^k+1},a_{2^k+2},\ldots,a_{2^{k+1}-1}$, and now I want to show that every subsequence $\displaystyle c_k$, as well as that the last element of $\displaystyle c_k$ is less than the first element of $\displaystyle c_{k+1}$ so that there is an increase in the "boundary" when the coefficient by $\displaystyle a_0$ changes --and that's what I have most problems with. Could you help me out?