# How to solve a ceiling expression or recurrence equation?

I am trying to express the following in term of n, $$\underbrace{\hbox{ \left \lceil \frac{3}{2}.\left \lceil { \frac{3}{2}.\left \lceil { \ldots \left \lceil \frac{3}{2}.\left \lceil { \frac{3}{2}.2 } \right \rceil \right \rceil \ldots } \right \rceil } \right \rceil \right \rceil}}_{\hbox{n times}}$$ We can easily see that, if there exits no ceil in the expression, then it is equal to $2.(\frac{3}{2})^{n}$. But in this case, is it might equal to $2.(\frac{3}{2})^{n} + f(n)$ ?

Also, when we think as each $\frac{3}{2}=1+\frac{1}{2}$, this problem is equal to following recurrence equation $$a_n=a_{n-1}+ \left \lceil \frac{a_{n-1}}{2} \right \rceil$$ where $a_0=2$, $a_1=3$, $a_2=5$. If this recurrence can be expressed in term of n, this will correspond to the problem.

I don't know whether it works.

Do you have any idea about that ?

• I'd start by unrolling a few times. I have the hunch that the terms will end up being a simple sequence of integers, or at least give you a conjecture of their form that you then prove by induction. – vonbrand Feb 4 '14 at 15:58
• Related oeis.org/A061419 – Dr. Wolfgang Hintze Oct 2 '18 at 8:02

The recursion is known, and I'd like to compile the main results here. Then I touch briefly the extension to other starting values, and the relation to the Collatz problem.

The known facts

Let us write the recursion as

$$c_{n} = \lceil \frac{3}{2} c_{n-1} \rceil, n= 1,2,...\tag{1}$$

For $$c_0 = 1$$ the first few terms are

$$t_1 = 1,2,3,5,8,12,18,27,41,62,93,140,210,315,473,710,...\tag{2}$$

The sequence $$t_1$$ is contained in OEIS as https://oeis.org/A061419, a(n) = ceiling(a(n-1)*3/2) with a(1) = 1.

The sequence grows exponentially, and for $$n\to\infty$$ the quotient approaches a constant

$$c_{n}/ \left(\frac{3}{2}\right)^n\to a_{4}\tag{3}$$

Where $$a_{4} = K(3) = 1.62227050288476731595695...$$ is a constant related to the Josephus problem (https://oeis.org/A083286).

Even an exact expression was derived (see http://mathworld.wolfram.com/PowerCeilings.html)

$$c_{n} = \left\lfloor a_{4} \left(\frac{3}{2}\right)^n\right\rfloor\tag{4}$$

Here $$\lfloor x \rfloor$$ is the floor function of $$x$$.

The accuracy of the expression $$c_{n}$$ calculated by (4) depends, of course, on the number of exact digits of $$a_{4}$$.

Extension to other starting values

Other starting values $$c_0$$ lead to different series. Take as a new starting value the first integer which is missing in the sequence of all series obtained so far.

Now, as no term in $$t_1$$ except the first one has the form $$3k+1$$ (proof below), the next starting value is $$3*1+1 = 4$$. This generalizes: new series are generated by starting values

$$c_{0,k} = 3k+1, k = 1, 2, ...$$

The missing proof follows immediately from rewriting the recursion relation (1) as

$$c_{n} = \begin{cases} 3 \left(\frac{c_{n-1}}{2}\right), & \text{if c_{n-1} is even} \\ 3 \left(\frac{c_{n-1}-1}{2}\right)+2, & \text{if c_{n-1} is odd} \end{cases}\tag{5}$$

which shows that $$(c_{n} \bmod 3)\ne 1$$.

The first few new starting values are thus 4, 7,10, 13. Non of these series are in OEIS.

We have

$$t_4 = 4,6,9,14,21,32,48,72,108,162,243,365,548,822,1233,1850,...$$ $$t_7 = 7,11,17,26,39,59,89,134,201,302,453,680,1020,1530,2295,3443,...$$ $$t_{10}= 10,15,23,35,53,80,120,180,270,405,608,912,1368,2052,3078,4617,...$$ $$t_{13} = 13,20,30,45,68,102,153,230,345,518,777,1166,1749,2624,3936,5904,...$$

The asmptotic behaviour of the quotients is similar to (3) just with other values of the constant. Naming the constant as $$a_{c_0}$$ we find

$$a_{4} = 4.22592..., a_{7} = 7.86418..., a_{10} = 10.544..., a_{13} = 13.483...$$

The exact formulas are similar to (4) with the correspoding constant $$a_{c_0}$$.

Relation to the Collatz conjecture

The factor $$\frac{3}{2}$$ arouse my suspicion that the problem might be related to the famous Collatz conjecture(https://de.wikipedia.org/wiki/Collatz_Conjecture).

And, indeed, replacing the factor $$3$$ by $$1$$ in the first equation of (5) gives the recursion relation of the Collatz problem.

One of the many differences between the power ceiling sequences (pcs) (1) and the Collatz series is that a pcs is completely determined by any of its elements while different Collatz series can have elements in common.

In fact, recursion (5) can be uniquely inverted

$$c_{n-1} = \begin{cases} 2 \left(\frac{c_{n}}{3}\right), & \text{if 3|c_{n} }\\ 2 \left(\frac{c_{n}-2}{3}\right)+1, & \text{if 3|(c_{n}-2)} \end{cases}\tag{6}$$

The backward series stops if $$3|(c_{n}-1)$$.