Republic of Mathematics blog

Growth rates of simple integer recurrences

Posted by: Gary Ernest Davis on: June 5, 2012

The sequence of integers A(n) defined by A(1)=2 \textrm{ and } A(n)= \lfloor(3/2)A(n-1)\rfloor – where \lfloor x\rfloor , the floor of x , is the greatest integer \leq x – begins 2, 3, 4, 6, 9, 13, 19, 28, 42, 63, 94, 141, 211, 316, 474, 711, 1066, 1599, 2398, 3597, 5395, 8092, 12138, 18207, 27310, 40965, 61447, 92170, 138255, 207382, 311073 and grows rapidly.

One can numerically estimate the growth rate of this sequence by first observing that the sequence of positive numbers \frac{A(n)}{(3/2)^n} is decreasing. This follows from the inequality A(n) =\lfloor(3/2)A(n-1)\rfloor \leq (3/2)A(n-1) upon dividing by (3/2)^n, to get \frac{A(n)}{(3/2)^n}\leq \frac{A(n-1)}{(3/2)^{n-1}}.

This means the sequence \frac{A(n)}{(3/2)^n} has a limit. In fact this sequence converges fairly rapidly to the limit:

n A(n)/(3/2)n n A(n)/(3/2)n
1 1.33333333333 34 1.08151439525
2 1.33333333333 35 1.08151405187
3 1.18518518519 36 1.08151382295
4 1.18518518519 37 1.08151382295
5 1.18518518519 38 1.08151382295
6 1.14128943759 39 1.08151375512
7 1.11202560585 40 1.08151375512
8 1.09251638470 41 1.08151372497
9 1.09251638470 42 1.08151370487
10 1.09251638470 43 1.08151369148
11 1.08673587473 44 1.08151368254
12 1.08673587473 45 1.08151367659
13 1.08416675918 46 1.08151367262
14 1.08245401549 47 1.08151366997
15 1.08245401549 48 1.08151366997
16 1.08245401549 49 1.08151366880
17 1.08194653587 50 1.08151366880
18 1.08194653587 51 1.08151366880
19 1.08172098938 52 1.08151366880
20 1.08172098938 53 1.08151366880
21 1.08162074649 54 1.08151366880
22 1.08155391790 55 1.08151366869
23 1.08155391790 56 1.08151366862
24 1.08155391790 57 1.08151366862
25 1.08153411684 58 1.08151366862
26 1.08153411684 59 1.08151366860
27 1.08152531636 60 1.08151366860
28 1.08151944938 61 1.08151366859
29 1.08151944938 62 1.08151366859
30 1.08151684183 63 1.08151366859
31 1.08151684183 64 1.08151366859
32 1.08151568292 65 1.08151366859
33 1.08151491032 66 1.08151366859

x

So we see that A(n)\approx 1.08151366859(3/2)^n for large n.

What if we replace the constant 3/2 by a parameter r ?

How does the sequence A(n) defined by A(1)=2 \textrm{ and } A(n)= \lfloor rA(n-1)\rfloor grow?

As before we see there is a constant K(r) such that A(n)/r^n \to K(r) \textrm{ as } r \to \infty

An obvious question is: how does K(r) \textrm{ vary with } r ?

A moment’s thought shows that the answer is only interesting for r \geq 3/2

The following Mathematica® code computes K(r) to a decent approximation:

A[1, r_] = 2;
A[n_, r_] := A[n, r] = Floor[r*A[n – 1, r]];
T = Table[{r, Table[N[A[n, r]/r^n], {n, 1, 100}][[-1]]}, {r, 1.5, 5, 0.001}];
ListPlot[T, Joined -> True]

and the resulting plot of K(r) \textrm{ versus } r looks as follows:

A blow-up of the portion of the plot for 1.5 \leq r \leq 2.5 looks as follows:

1 Response to "Growth rates of simple integer recurrences"

Some questions that came to my mind as I read this:

1. Is K(r) rational or irrational? Algebraic or transcendental?
2. How does the initial value of the sequence change the behavior of the sequence?

Something for me to play around with in my spare time. Thanks!

Leave a Reply to Andy Cancel reply