Integers sequence

Printable View

March 12th 2010, 06:48 AM
atreyyu

Integers sequence

Show that the sequence of positive integers given by $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 $a$ and eventually showing that the argument is proved by the contradiction $1\geq 2$ , and now I'm not all that sure it is correct. Do you have any better ideas?
March 12th 2010, 11:14 AM
running-gag

Hi

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

given $a_0$

for every p integer

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

$a_n = 3^{p+1} a_0 + \alpha_n$ where $(\alpha_n)$ is a strictly increasing sequence of positive integers
March 12th 2010, 01:36 PM
atreyyu

Quote:

Originally Posted by running-gag

Hi

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

given $a_0$

for every p integer

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

$a_n = 3^{p+1} a_0 + \alpha_n$ where $(\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?
March 12th 2010, 02:07 PM
icemanfan

Quote:

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 $a_1$ , you get

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

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

and so on.

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

You also need to show that for each n, $a_x < a_y$ , where $x = 2^n - 1$ and $y = 2^n$ .
March 13th 2010, 03:05 AM
atreyyu

Ok, I decided to state that $a$ is composed of subsequences $c_k$ , where $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 $c_k$ , as well as that the last element of $c_k$ is less than the first element of $c_{k+1}$ so that there is an increase in the "boundary" when the coefficient by $a_0$ changes --and that's what I have most problems with. Could you help me out?