Competition problem — Algebra — Maths Olympiad Prep

Algebra Difficulty 6.2 National olympiad Prove it Brazil

Any positive integer $n$ can be written in the form $n = 2^b(2c + 1)$ . We call $2c + 1$ the *odd part of* $n$ . Given an odd integer $n > 0$ , define the sequence $a_0, a_1, a_2, \ldots$ as follows: $a_0 = 2^n - 1$ , $a_{k+1}$ is the odd part of $3a_k + 1$ . Find $a_n$ .

Solution

An induction shows that $a_k = 3^k 2^{n-k} - 1$ for $k \le n-1$ . It is certainly true for $k=0$ . Suppose it is true for $k < n-1$ . Then $3a_k + 1 = 3^{k+1} 2^{n-k} - 2$ . Since $n-k > 1$ , the odd part is $3^{k+1} 2^{n-(k+1)} - 1$ , so the result is true for $k+1$ . That gets us as far as $a_{n-1} = 3^{n-1} 2 - 1$ .

Now we want the odd part of $2(3^n - 1)$ . Certainly $3^n - 1$ is even. We have $3^n - 1 \equiv (-1)^n - 1 \equiv 2 \pmod 4$ for $n$ odd, so for $n$ odd it is not divisible by 4. Hence for $n$ odd we have $a_n = \frac{3^{n-1}}{2}$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.