6

This is my first post here, thanks for stopping by. The question as written below comes from the book 'A Concise Introduction To Pure Mathematics'. I've included my working (this isn't a homework problem) and points I am interested in - particularly, the thought process that you had in dealing with this problem.

Critic Ivor Smallbrain has been keeping a careful account of the number of chocolate bars he has eaten during film screenings over his career. For each positive integer $n$ he denotes by $a_n$ the total number of bars he consumed during the first n films. One evening, during a screening of the Christmas epic It's a Wonderful Proof, he notices that the sequence $a_1 , a_2 , ...$ obeys the following rules for all $ n => 1$:

$a_{n+1} > a_n $

$a_{a_n} = 3n$

Also $a_1 > 0$

(a) Find $a_1$ . (Hint: Let $x=a_1$. Then what is $a_x$?)

(b) Find $a_2 , a_3 , ... , a_8 , a_9$

(c) Find $a_{100}$

(d) Investigate the sequence $a_1 , a_2 , ...$ further.

(a) Well, we would be good to make use of the hint, so that $a_x = a_{a_1} = 3$ by the second property. Now, let us say that x is greater than or equal to four. As the sequence is strictly increasing, the terms before $a_x$ are strictly decreasing, thus we would run out of terms if this were the case. Hence x must be less than 4, so x is 1,2 or 3, remembering that the first term of the sequence is at least one.

Well, suppose that x is 1. Then we get $a_1 = a_x = a_{a_1} = 3$, an absurdity.

So, we investigate if x is 3. Then $a_3 = a_x = a_{a_1} = 3$ Yet we recall x is $a_1$ and the sequence is strictly increasing, so this is an absurdity.

(b) Knowing that $a_1 = 2$ we note $3 = a_{a_1} = a_2$ by the second property. Similarly, $6=a_{a_2}=a_3$ so $9 = a_{a_3} = a_6$. Now, we are looking for $a_5$ and $a_4$, but this is made easy by the first property; the sequence is increasing, and the third term is 6, the sixth term is 9. Hence the fourth is 7 and the fifth 8. So, to sum;

$a_1$ = 2 $a_2$ = 3 $a_3$ = 6 $a_4$ = 7 $a_5$ = 8 $a_6$ = 9

To finish, note the seventh term is obtained from the fourth, to be 12,the eighth from the fifth, to be 15, and the ninth from the sixth, to be 18.

(c) -

(d) -

Parts I am stuck on. Well, it sounds like if you could answer (d) with an explicit formula then obtaining the answer for (c) would be fine - you just plug in n = 100. However, I am struggling to find how you can 'skip' finding numbers. From the working above it appears to me that I need to find all terms before the hundredth.

I am asking for your help in not merely a method, but in illumination - please explain to me why you are doing this or that and so forth - I am hoping to learn something here, and if you can answer this, then whatever you say will be something I and all people can learn from so do not hold back - say anything.

WierdFishes
  • 151

1 Answers1

1

This is one of my favorite problems! One way to proceed here is by induction, and for this, since the multiplication in the recursive formula is by $3$, it may help to write integers in base $3$. Then the induction hypothesis looks like this. Let $f(n)=a_n$ for $n\ge 1$, and let $n$ in base $3$ be $n=a_{k+1} a_{k}\dots a_1a_0$ (as a string of digits), then $$ f(1a_k\dots a_1 a_0)=2a_k\dots a_1 a_0, \quad f(2a_k\dots a_1 a_0)=1a_k\dots a_1 a_0 0. $$ In other words, $$ a_n=f(n)= \begin{cases} n+3^k, & \text{ if } 3^k\le n\le 2\cdot 3^k,\\ 3n-3^{k+1}, & \text{ if } 2\cdot 3^k\le n\le 3^{k+1}, \end{cases} $$ where $k=\left\lfloor\log_3 n\right\rfloor\ge 0$.

Notice also that $$ n+3^k=3n-3^{k+1}=3^{k+1} \quad \text{when} \quad n=2\cdot 3^k, $$ and $$ n+3^{k+1}=3n-3^{k+1}=2\cdot 3^{k+1} \quad \text{when} \quad n=3^{k+1}. $$

Since you seem to be asking for a hint rather than for a complete solution, I will leave it here and let you carry out the induction.

Alexander Burstein
  • 4,145