Of elementary general terms

Happy new year!

• Updated on 2 January: Strengthened the last proposition (removing the requirement of being integer-valued of the upper bound) and added more discussion on the elementariness of integer sequences. You are also welcome to discuss the problem in this Zhihu question (Chinese only).
• Updated on 3 January: Solved the problem whether all sequences of integer are elementary with an affirmative answer.

This entry is an extended discussion of a construction of general term formulae for certain integer-valued sequences using only elementary functions that happened when I was at senior high school. The idea presented in this article can be found in this post in Baidu Tieba (sorry if you cannot read Chinese; a backup version is available in case the original post becomes unavailable).

With the background and motivation stated, the first part gives the construction, which was work done at senior high school. The first part suggests that insisting on looking for an elementary formula for all sequences is a waste of time by demonstrating some ‘pathological’ elementary expressions. The second part is the extended discussion on integer-valued sequences and their general terms, which concludes an interesting equivalence: A sequence of integers is elementary if and only if it is bounded by some elementary sequence of integers. That is, the elementariness is downward monotonic. This property leaves a problem open: Do all integer-valued sequences have an elementary general term?

Background and motivation

There are people out there who insist finding an elementary formula for general terms of any random sequence (note: ‘random’ here means ‘coming from nowhere or anywhere’, not ‘stochastic’). People have wasted a huge amount of precious time in solving recurrences that are not ‘expressible by elementary functions’. More of them (the problems) are simply not created with the intention that a simple general term formula is available.

The purpose of this discussion is to stop people from stupidly pursuing an elementary general term. Instead, you should focus on properties of sequences that are more interesting.

Let’s get some definitions. Elementary functions are defined inductively:

• Constants, the power function (meaning $\left({x,y}\right)\mapsto x^y$, if $y$ is integral, $x$ is allowed to be negative, and if $y$ is non-negative, $x$ is allowed to be zero), the cosine function, the (natural) logarithm function, and the arc-from-sine function (with principal value choice $\arcsin x\in[{-\frac\pi2,\frac\pi2}]$), these are called 0-elementary functions.
• Addition, multiplication or composition of $k$-elementary functions is called a $({k+1})$-elementary function.
• A function is elementary if and only if it is $k$-elementary for some natural number $k$.
• Elementary functions take their natural domain, the set of values of variables in which all subexpressions of the function is valid, as the domain.

The definition coincides with that taught in senior high schools in China, and most calculus courses in universities in China. Categorisation of functions into elementary and non-elementary is not that interesting (somehow interesting, I’d say). Usually the functions we do computation on in exercises and exams are elementary, because their notations are widely accepted.

Anecdote The entrance exam of ENS of 1995 involved the study of elementary functions. A refined definition of elementary functions makes them form a differential field. By following the instruction of the exam, one gradually reaches the conclusion that $\int_0^x{e^{t^2}\mathrm{d}t}$ is not an elementary function. If you’re interested, Louville and search engines are your friends.

Let’s take two examples.

Example 1 Let $a_n$ be Fibonacci sequence, i.e., $a_{n+2}=a_{n+1}+a_n$ with initial values $a_0=0,a_1=1$. How can one find the general term as an elementary function of $n$?

There are many approaches to this problem. Power of matrix, repeated iteration of linear homomorphism, generatingfunctionological methods, characteristic polynomials, linear spaces, you name them. However, it is important that this sequence admits an elementary formula, namely $a_n=x_1y_1^n+x_2y_2^n$, where $x_1,x_2$ are some constants, and that $y_1,y_2$ are the two roots of $x^2=x+1$.

Example 2 Let $p_n$ be the sequence of primes, i.e., $p_n$ is the $n$-th prime number.

It is generally accepted that there seems to be no elementary function $f(x)$ such that $f(x)$ is defined on all positive integers and $p_n=f(n)$.

This is plainly wrong.

Construction

Before we give a construction, some definitions are needed:

Definition 1 A function $a:\mathbb{N}\mapsto\mathbb{R}$ is called a (real-valued) sequence. We often write $a_n$ for $a(n)$.

Definition 2 A sequence $a$ is said to be elementary, if and only if there exists an elementary function $f$ whose domain covers $\mathbb{N}$ such that $a_n=f(n)$ for all $n\in\mathbb{N}$. In other words, $a$ is elementary if and only if it is the restriction of some elementary function.

Definition 3 A positive-integer-valued sequence $a$ is said to grow slowly if there exists an elementary integer-valued sequence $b$ such that $a_n<2^{b_{n+1}-b_n}$ for all $n\in\mathbb{N}$. We say $a$ grows slowly thanks to $b$.

That is to say, if the number of digits of a sequence of positive integers is bounded by the differentiation of an elementary integer-valued sequence, the bounded sequence ‘grows slowly’.

Theorem Any slowly growing sequence is also elementary.

Lemma The function $x\mapsto\{x\}$ (the decimal part of $x$) defined on $\mathbb{R}\setminus\mathbb{Z}$ is elementary. So is $x\mapsto\lfloor x\rfloor$ (the integral part of $x$) defined on the same set.

Proof The cotangent function, $\cot x$, is elementary because $\cot x=\frac{\cos x}{\cos\left({x-\frac\pi2}\right)}$. The arctangent function is elementary because $\arctan x=\arcsin\frac{x}{\sqrt{1+x^2}}$. Therefore, $\{x\} = \frac12 - \frac1\pi\arctan\cot(\pi x)$ is elementary. And finally so is $\lfloor x\rfloor=x-\{x\}$.

Proof Let $a$ grow slowly thanks to $b$. We define $C=\sum_{k=0}^{+\infty}{a_k2^{-b_{k+1}-k}}.$ We first show that the definition of $C$ converges. Since $0<a_k<2^{b_{k+1}-b_k}$, we know that $b_{k+1}\geq b_k\geq b_0$ and $a_k2^{-b_{k+1}-k}<2^{-b_k-k}\leq 2^{-b_0-k}$. The summation is of non-negative terms and bounded, therefore convergent. Though $C$ is defined using $a$, it nevertheless is a constant, hence an elementary function.

Intuitively speaking, $C$ stores the numbers in its digits. Now we will ‘extract’ the digits from $C$. For $n$, we have $2^{b_n+n-1}C=\left({\sum_{k<n}+\sum_{k\geq n}}\right){a_k2^{b_n-b_{k+1}+n-k-1}},$ it can be verified that the second term is positive and less than 1, and obviously the first term is integral, therefore $\left\{2^{b_n+n-1}C\right\}$ is the second term. Now consider $2^{b_{n+1}-b_n+1}\left\{2^{b_n+n-1}C\right\}=a_n+\sum_{k>n}{a_k2^{b_{n+1}-b_{k+1}+n-k}},$ with exactly the same argument we have $a_n=\left\lfloor 2^{b_{n+1}-b_n+1}\left\{2^{b_n+n-1}C\right\}\right\rfloor,$ i.e., $a$ is elementary. Note that it is important that the second term strictly greater than 0 and strictly less than 1, which ensures the application of decimal/integral part function is elementary.

Example The sequence $a_n=1$ can be rewritten as $a_n=\left\lfloor 4\left\{2^{2n}3^{-1}\right\}\right\rfloor$.

Exercise Now that formulae are found for slowly growing sequences, they can be used to create more complicated ones. The readers are invited to think how the formula can be used to find a general term as elementary function for:

• $a_n=n!$
• $\displaystyle a_n=\sum_{k=1}^{n}{\frac1k}$
• $a_n=\sqrt{p_n}$

Having demonstrated this pathological construction, I assume I have successfully stopped some people from insisting on an elementary general term of all sequences.

Extended discussion

The converse of the construction proposition also holds. I.e., if a sequence of positive integers is elementary, it must grow slowly. The proof is so simple that I wondered if I was a fool to not come up with it until recently.

Proof Let $a$ be an elementary sequence of positive integers. Let $b_n=1+\min\mathop{\mathrm{argmax}}_{0\leq k\leq n}{a_k},$ then $b_n\leq n+1<2^{{\left({n+1}\right)}^2-n^2}$, i.e., $b$ grows slowly hence is elementary. Let $c_n=na_{b_n-1}+2n,$ then $c$ is elementary. Observe that $c_{n+1}-c_n\geq a_{b_n-1}+2>a_n+1$, therefore, $a_n<2^{c_{n+1}-c_n}$, i.e., $a$ grows slowly thanks to $c$.

Remark The definition of slow growth characterises positive-integer-valued sequences with elementary general term.

Now we’re ready to prove the so-called downward monotonicity of elementariness of integer-valued sequences.

Theorem An integer-valued sequence is elementary if and only if it is bounded by some elementary integer-valued sequence.

Proof Let $a$ be an integer-valued sequence. If $a$ is elementary, then $|a_n|\leq|a_n|$, i.e., bounded by an elementary integer-valued sequence (the absolute value of itself). Conversely, if $|a_n|\leq b_n$ for some elementary integer-valued sequence $b$, we know that $c_n=|a_n|+1$ grows slowly thanks to $d_n=2n+n\max_{0\leq k\leq n}{b_n},$ therefore, $c_n$ is elementary. Moreover, $e_n=2+\mathop{\mathrm{sgn}}{a_n}$ grows slowly thanks to $f_n=2n$ hence also elementary. Finally $a_n=\left({c_n-1}\right)\left({e_n-2}\right)$ is elementary.

Question There’s a problem left open (see the update):

Are all integer-valued sequences elementary?

Due to downward monotonicity, the problem is equivalent to: Is there a sequence of integers that grows faster than all elementary integer-valued sequences? (See the update.) The problem is hard partly because some elementary functions are hard to analyse when restricted to $\mathbb{Z}$, for example, $\left\lfloor\tan{n}\right\rfloor$ and the functions constructed in the first part.

Updated on 2 January

The requirement of $b$ being integer-valued can be removed from the last proposition. To prove this, we shall assume $b$ is an elementary real-valued sequence and find an elementary integer-valued sequence $b'$ that is point-wise greater than $b$.

Consider $S=\left\{{\left\{b_n\right\}:n\in\mathbb{N}}\right\}$ (the set of decimal parts of terms of $b$), which is at most countable. Take some $s\in{{\left[{0,1}\right)}\setminus S}$ and define $b_n'=\left\lfloor{b_n+1-s}\right\rfloor+1.$ Observe that $b_n+1-s$ is never an integer, therefore, $b'$ is elementary. Moreover, $b_n'\geq b_n+1-s-1+1>b_n$.

Equivalent problem The original equivalent formulation is wrong. The correct version is: Is there a sequence of integers that cannot be upper-bounded by any elementary sequence?

That a sequence is not upper-bounded by another does not imply the former grows faster than the latter. In fact:

Proposition There is no sequence that grows faster than all elementary sequences. In other words, for all sequence $a$, there exists an elementary sequence $d$ such that for all $N$, there exists $n>N$ such that $|a_n|<d_n$.

Proof Let $a$ be any sequence, define $b_n=n^2+n+1+\sum_{k=0}^{n}{\lfloor|a_k|\rfloor},$ then $b$ is strictly increasing, and $b_n>|a_n|,b_n>n$ for all $n\in\mathbb{N}$. Now let $c_0=1+b_0,\ c_{n+1}=1+b_{c_n},$ then $c_n>b_n$ and $c_{n+1}>1+c_n$ for all $n\in\mathbb{N}$. Define a constant $C=\sum_{k=0}^{+\infty}{2^{-c_k}},$ which obviously converges and is irrational. Define $d_n=\left\lfloor\frac{3}{2^{1-n}\left\{{2^nC}\right\}}\right\rfloor+1.$ Since $C$ is irrational, $d$ is elementary. Observe that $\begin{aligned}d_{c_n}&{}>\frac{3}{2\sum_{k\geq n+1}{2^{-c_k}}}\\\\&{}\geq\frac{3}{2\left({2^{-c_{n+1}}+2^{-c_{n+1}-1}}\right)}\\\\&{}=2^{c_{n+1}}>c_{n+1}>b_{c_n}>|a_{c_n}|,\end{aligned}$ which implies that $a$ does not grow faster than $d$, an elementary sequence.

Updated on 3 January

The answer to the previous problem is affirmative. Following the path of proving that no sequence grows faster than all elementary sequences, continue to define $e_n=1+({n+1})\max_{0\leq k\leq n}{d_k},$ which is elementary, positive, integer-valued and strictly increasing. Now we further compose this function to define $f_n=e_{e_n}.$ Note $e_n>d_n$, therefore, $e_{c_n}>d_{c_n}>c_{n+1}>b_{c_n}.$ Together with the monotonicity of $e$, we obtain $f_{c_n}=e_{e_{c_n}}>e_{c_{n+1}}>b_{c_{n+1}}.$ Since $f,b,c$ are both strictly increasing, for $n\geq c_0$, there exists $k$ such that $c_k\leq n<c_{k+1}$, which gives $f_n\geq f_{c_k}>b_{c_{k+1}}>b_n>|a_n|.$ Moreover, for $n<c_0$ we have $|a_n|<b_n<b_{c_0}$. Therefore, $a$ is bounded by $b_{c_0}+f$, an elementary sequence. By the equivalence, if $a$ is integer-valued, it is elementary.

Remark Bo Hu points out that $d$ is already increasing: actually for $c_n\leq k<c_{n+1}$, $d_k$ remains a constant and is around $2^{c_{n+1}}$.

Acknowledgement

The idea of the update on 2 January was inspired by this Zhihu answer of Zhihu user Monsieur TRISTE. Specifically, his idea suggested using the place of digits to encode function value.

Bo Hu points out that the proof of the final proposition can be simplified.