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 (x,y)xy\left({x,y}\right)\mapsto x^y, if yy is integral, xx is allowed to be negative, and if yy is non-negative, xx is allowed to be zero), the cosine function, the (natural) logarithm function, and the arc-from-sine function (with principal value choice arcsinx[π2,π2]\arcsin x\in[{-\frac\pi2,\frac\pi2}]), these are called 0-elementary functions.
  • Addition, multiplication or composition of kk-elementary functions is called a (k+1)({k+1})-elementary function.
  • A function is elementary if and only if it is kk-elementary for some natural number kk.
  • 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 0xet2dt\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 ana_n be Fibonacci sequence, i.e., an+2=an+1+ana_{n+2}=a_{n+1}+a_n with initial values a0=0,a1=1a_0=0,a_1=1. How can one find the general term as an elementary function of nn?

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 an=x1y1n+x2y2na_n=x_1y_1^n+x_2y_2^n, where x1,x2x_1,x_2 are some constants, and that y1,y2y_1,y_2 are the two roots of x2=x+1x^2=x+1.

Example 2 Let pnp_n be the sequence of primes, i.e., pnp_n is the nn-th prime number.

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

This is plainly wrong.

Construction

Before we give a construction, some definitions are needed:

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

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

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

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{x}x\mapsto\{x\} (the decimal part of xx) defined on RZ\mathbb{R}\setminus\mathbb{Z} is elementary. So is xxx\mapsto\lfloor x\rfloor (the integral part of xx) defined on the same set.

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

Proof Let aa grow slowly thanks to bb. We define C=k=0+ak2bk+1k.C=\sum_{k=0}^{+\infty}{a_k2^{-b_{k+1}-k}}. We first show that the definition of CC converges. Since 0<ak<2bk+1bk0<a_k<2^{b_{k+1}-b_k}, we know that bk+1bkb0b_{k+1}\geq b_k\geq b_0 and ak2bk+1k<2bkk2b0ka_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 CC is defined using aa, it nevertheless is a constant, hence an elementary function.

Intuitively speaking, CC stores the numbers in its digits. Now we will ‘extract’ the digits from CC. For nn, we have 2bn+n1C=(k<n+kn)ak2bnbk+1+nk1,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 {2bn+n1C}\left\{2^{b_n+n-1}C\right\} is the second term. Now consider 2bn+1bn+1{2bn+n1C}=an+k>nak2bn+1bk+1+nk,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 an=2bn+1bn+1{2bn+n1C},a_n=\left\lfloor 2^{b_{n+1}-b_n+1}\left\{2^{b_n+n-1}C\right\}\right\rfloor, i.e., aa 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 an=1a_n=1 can be rewritten as an=4{22n31}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:

  • an=n!a_n=n!
  • an=k=1n1k\displaystyle a_n=\sum_{k=1}^{n}{\frac1k}
  • an=pna_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 aa be an elementary sequence of positive integers. Let bn=1+minargmax0knak,b_n=1+\min\mathop{\mathrm{argmax}}_{0\leq k\leq n}{a_k}, then bnn+1<2(n+1)2n2b_n\leq n+1<2^{{\left({n+1}\right)}^2-n^2}, i.e., bb grows slowly hence is elementary. Let cn=nabn1+2n,c_n=na_{b_n-1}+2n, then cc is elementary. Observe that cn+1cnabn1+2>an+1c_{n+1}-c_n\geq a_{b_n-1}+2>a_n+1, therefore, an<2cn+1cna_n<2^{c_{n+1}-c_n}, i.e., aa grows slowly thanks to cc.

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 aa be an integer-valued sequence. If aa is elementary, then anan|a_n|\leq|a_n|, i.e., bounded by an elementary integer-valued sequence (the absolute value of itself). Conversely, if anbn|a_n|\leq b_n for some elementary integer-valued sequence bb, we know that cn=an+1c_n=|a_n|+1 grows slowly thanks to dn=2n+nmax0knbn,d_n=2n+n\max_{0\leq k\leq n}{b_n}, therefore, cnc_n is elementary. Moreover, en=2+sgnane_n=2+\mathop{\mathrm{sgn}}{a_n} grows slowly thanks to fn=2nf_n=2n hence also elementary. Finally an=(cn1)(en2)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 Z\mathbb{Z}, for example, tann\left\lfloor\tan{n}\right\rfloor and the functions constructed in the first part.

Updated on 2 January

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

Consider S={{bn}:nN}S=\left\{{\left\{b_n\right\}:n\in\mathbb{N}}\right\} (the set of decimal parts of terms of bb), which is at most countable. Take some s[0,1)Ss\in{{\left[{0,1}\right)}\setminus S} and define bn=bn+1s+1.b_n'=\left\lfloor{b_n+1-s}\right\rfloor+1. Observe that bn+1sb_n+1-s is never an integer, therefore, bb' is elementary. Moreover, bnbn+1s1+1>bnb_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 aa, there exists an elementary sequence dd such that for all NN, there exists n>Nn>N such that an<dn|a_n|<d_n.

Proof Let aa be any sequence, define bn=n2+n+1+k=0nak,b_n=n^2+n+1+\sum_{k=0}^{n}{\lfloor|a_k|\rfloor}, then bb is strictly increasing, and bn>an,bn>nb_n>|a_n|,b_n>n for all nNn\in\mathbb{N}. Now let c0=1+b0, cn+1=1+bcn,c_0=1+b_0,\ c_{n+1}=1+b_{c_n}, then cn>bnc_n>b_n and cn+1>1+cnc_{n+1}>1+c_n for all nNn\in\mathbb{N}. Define a constant C=k=0+2ck,C=\sum_{k=0}^{+\infty}{2^{-c_k}}, which obviously converges and is irrational. Define dn=321n{2nC}+1.d_n=\left\lfloor\frac{3}{2^{1-n}\left\{{2^nC}\right\}}\right\rfloor+1. Since CC is irrational, dd is elementary. Observe that dcn>32kn+12ck32(2cn+1+2cn+11)=2cn+1>cn+1>bcn>acn,\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 aa does not grow faster than dd, 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 en=1+(n+1)max0kndk,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 fn=een.f_n=e_{e_n}. Note en>dne_n>d_n, therefore, ecn>dcn>cn+1>bcn.e_{c_n}>d_{c_n}>c_{n+1}>b_{c_n}. Together with the monotonicity of ee, we obtain fcn=eecn>ecn+1>bcn+1.f_{c_n}=e_{e_{c_n}}>e_{c_{n+1}}>b_{c_{n+1}}. Since f,b,cf,b,c are both strictly increasing, for nc0n\geq c_0, there exists kk such that ckn<ck+1c_k\leq n<c_{k+1}, which gives fnfck>bck+1>bn>an.f_n\geq f_{c_k}>b_{c_{k+1}}>b_n>|a_n|. Moreover, for n<c0n<c_0 we have an<bn<bc0|a_n|<b_n<b_{c_0}. Therefore, aa is bounded by bc0+fb_{c_0}+f, an elementary sequence. By the equivalence, if aa is integer-valued, it is elementary.

Remark Bo Hu points out that dd is already increasing: actually for cnk<cn+1c_n\leq k<c_{n+1}, dkd_k remains a constant and is around 2cn+12^{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.

Please enable JavaScript to view the comments powered by Disqus.