10
$\begingroup$

In school we teach arithmetic and geometric sequences. Students should notice that arithmetic sequences (with common difference greater than $0$) grow steadily, while geometric sequences (with common ratio greater than $1$) grow rapidly.

A natural question arises:

What kind of sequence is between an arithmetic and a geometric sequence?

(I will post my answer.)

$\endgroup$

4 Answers 4

15
$\begingroup$

Polynomials with $\textrm{degree}>1$ grow faster than arithmetic sequences but slower than geometric sequences.

More generally, after sufficiently many terms:

\begin{align*} & \textrm{logarithm}(n) \\ & \lll \textrm{radical}(n) \\ & \lll \textrm{linear}(n) \\ & \lll \textrm{polynomial}(n) \\ & \lll \textrm{exponential}(n) \\ & \lll \textrm{factorial}(n) \end{align*}

For example, consider the following sequences:

\begin{align*} \log_{2} n \lll \sqrt{n} \lll n \lll n^2 \lll 2^{n} \lll n! \end{align*}

Substituting $n=1000,$ we get

\begin{align*} & \log_{2}{1000} \approx 10 \\ & \lll \sqrt{1000} \approx 32 \\ & \lll 1000 = 10^3 \\ & \lll 1000^2 = 10^6 \\ & \lll 2^{1000} \approx 10^{301} \\ & \lll 1000! \approx 10^{2567} \end{align*}

$\endgroup$
5
  • $\begingroup$ Please give a sequence that's polynomial. $\endgroup$
    – Sue VanHattum
    Commented Jun 28 at 17:00
  • 2
    $\begingroup$ @SueVanHattum 1, 4, 9, 16, 25, 36, ... $\endgroup$
    – usul
    Commented Jun 28 at 18:01
  • 4
    $\begingroup$ It's worth mentioning asymptotic notation, which formalizes and extends these relationships. $\endgroup$
    – usul
    Commented Jun 28 at 18:02
  • $\begingroup$ @usul: Sure. I guess I meant something interesting, maybe from a real-life situation. But your partial sums answer is kind of what I was looking for. $\endgroup$
    – Sue VanHattum
    Commented Jun 28 at 18:29
  • 2
    $\begingroup$ @SueVanHattum: Polynomial sequences occur in abundance in the run-time analysis of computer algorithms. I listed a few classical examples in my answer. $\endgroup$ Commented Jun 28 at 21:27
14
$\begingroup$

The hidden connection between arithmetic and geometric sequences

enter image description here

If we stack circles on the function $y=|x|^\color{red}{1}$, the sequence of radii is geometric. (proof)
If we stack circles on the function $y=|x|^\color{red}{2}$, the sequence of radii is arthmetic. (proof)

So if you want to know what is exactly between an arithmetic and a geometric sequence, just consider a stack of circles on the function $y=|x|^\color{red}{1.5}$.

Call the sequence of their radii $\{r_n\}$. It turns out that as $r_1\to\infty$, $r_n$ approaches the $n^\text{th}$ term of a quadratic sequence, as I show below. (Most school students will not be able to understand the explanation, but they can at least understand the result.)


enter image description here

From the graph, we can see that as $\frac{r_2}{r_1}\to 1$, i.e. as the gradient of the curve approches infinity,

${r_1}+{r_2}=c_2-c_1\approx {t_2}^{1.5}-{t_1}^{1.5}\approx {r_2}^{1.5}-{r_1}^{1.5}$

$\therefore\lim\limits_{\frac{r_2}{r_1}\to 1}\frac{r_1+r_2}{{r_2}^{1.5}-{r_1}^{1.5}}=1$

$\begin{align} \lim\limits_{\frac{r_2}{r_1}\to 1}(\sqrt{r_2}-\sqrt{r_1})&=\lim\limits_{\frac{r_2}{r_1}\to 1}(\sqrt{r_2}-\sqrt{r_1})\left(\frac{r_1+r_2}{{r_2}^{1.5}-{r_1}^{1.5}}\right)\text{ using the previous result}\\ &=\lim\limits_{\frac{r_2}{r_1}\to 1}\left(\frac{r_1+r_2}{r_1}\right)\left(\frac{r_1\sqrt{r_2}-r_1\sqrt{r_1}}{{r_2}^{1.5}-{r_1}^{1.5}}\right)\text{ by rearranging}\\ &=2\lim\limits_{\frac{r_2}{r_1}\to 1}\frac{\left(\frac{r_2}{r_1}\right)^{0.5}-1}{\left(\frac{r_2}{r_1}\right)^{1.5}-1}\text{ by dividing top and bottom by ${r_1}^{1.5}$}\\ &=2\lim\limits_{\frac{r_2}{r_1}\to 1}\frac{0.5\left(\frac{r_2}{r_1}\right)^{-0.5}}{1.5\left(\frac{r_2}{r_1}\right)^{0.5}}\text{ by L'Hopital's rule}\\ &=\frac23\\ \end{align}$

So as $\frac{r_2}{r_1}\to 1$,

$\begin{align} \sqrt{r_n}&\approx\frac23+\sqrt{r_{n-1}}\\ &\approx\frac23+\frac23+\sqrt{r_{n-2}}\\ &\approx\frac23+\frac23+\frac23+\sqrt{r_{n-3}}\\ &\approx\dots\\ &\approx\frac23(n-1)+\sqrt{r_1}\\ \end{align}$

$\therefore r_n\approx \left(\frac23(n-1)+\sqrt{r_1}\right)^2$

That is, as $r_1\to\infty$, $r_n$ approaches the $n^\text{th}$ term of a quadratic sequence.


The three most commonly taught sequences in school are the arithmetic, geometric and quadratic sequences, but most students and teachers do not realize that they have this neat relationship.

$\endgroup$
3
  • 4
    $\begingroup$ Re: "So if you want to know what is exactly between an arithmetic and a geometric sequence, just consider a stack of circles on the function $y=|x|^\color{red}{1.5}$": Why 1.5 (the arithmetic mean of 1 and 2) instead of $\sqrt 2$ (their geometric mean)? $\endgroup$
    – ruakh
    Commented Jun 30 at 0:01
  • $\begingroup$ @ruakh Just as there are different definitions of "average", there are different definitions of "exactly between". They can all be investigated. I chose the arithmetic mean because it yields a nice result. $\endgroup$
    – Dan
    Commented Jun 30 at 0:49
  • 6
    $\begingroup$ I feel that as a student, this explanation would have confused me more rather than explained anything. But as a graduate, it's a neat one :) $\endgroup$
    – jpa
    Commented Jun 30 at 17:49
8
$\begingroup$

Since a comment asked for something from practical situations:

The runtime complexity of computer algorithms gives a huge variety of sequences with all kinds of growth behaviour - and understanding the runtime complexity is an important part of choosing an appropriate algorithm for a given task. For instance (I'm using Big $O$ notation):

  1. Linear search for a given element in an ordered list of $n$ elements: $O(n)$.

  2. Binary search for a given element in an ordered list of $n$ elements (assuming that you have random access in constant time to any element at any position in the list): $O(\log(n))$.

  3. Sorting a list of $n$ items with a comparative sorting algorithm such as e.g. merge sort: $O(n \log(n))$

  4. Sorting a list of $n$ items according to a key with fixed key length, with radix sort: $O(n)$

  5. Multiplying a non-sparse $n \times n$-matrix with a vector with $n$ entries: $O(n^2)$

  6. Multiplying two $n \times n$-matrices by simply applying the definition of the matrix product in each entry: $O(n^3)$

  7. Multiplying two $n \times n$-matrices by Strassen's algorithm: $\approx O(n^{2,81})$

  8. Computing the determinant of a non-sparse $n \times n$-matrix by using Leibniz' formula: $O((n+1)!)$

  9. Computing the determinant of a non-sparse $n \times n$-matrix by using Laplace development: somewhere between $O(n!)$ and $O((n+1)!)$ (Wikipedia claims it's $O(n!)$, but I'm a bit skeptical)

  10. Computing the determinant of a non-sparse $n \times n$-matrix by using Gauß elimination: $O(n^3)$

  11. Computing the $n$-th power of an element in a finite field of fixed cardinality: $O(\log(n))$

Examples 3, 5, 6, 7, and 10 have superlinear but subexponential growth, i.e., they are between arithmetic and geometric behaviour, as requested by the OP.

$\endgroup$
3
  • 1
    $\begingroup$ And of course there is always the classic: reading $n \times n$ matrix is $O(n^2)$ $\endgroup$
    – justhalf
    Commented Jun 30 at 15:00
  • 1
    $\begingroup$ the big O wiki link takes you to radix sort, btw $\endgroup$
    – texdr.aft
    Commented Jun 30 at 15:19
  • 1
    $\begingroup$ @texdr.aft: Thanks for the correction! $\endgroup$ Commented Jun 30 at 19:53
4
$\begingroup$

That's a fun geometric example! Mine are more combinatorial. As Justin's answer mentions, any sequence where terms grow polynomially (with degree greater than one) is an example.

For example, the perfect squares 1,4,9,16,25,36,.... Also perfect cubes, etc.

One place quadratic sequences come up is the partial sums of an arithmetic sequence (i.e. the sum of the first $n$ terms). For example it's well-known that with the sequence 1,3,5,7,9, ..., the partial sums are the perfect squares. This hints at calculus (one can give a picture of the total area of a sequence of width-1 rectangles with height 1,3,5,...).

Cubic sequences can come up as the partial sums of a quadratic sequence.

Maybe another natural example is the number of ways to pick $k$ items from a set of size $n$, for $n=k,...$. You can use stories around this, for example, the sequence of how many handshakes there are in a meeting of $n$ people.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.