1

Is there always an algebraic expression from which we can derive any arbitrary and arbitrary large series of natural numbers (greater than zero)? For instance, if we have $1, 2, 4, 8, 16$ a possible expression is $\frac{(2^n)}{2}$ (starting from n=1). Now, let's suppose we have all the natural exponents all the way to $2^{10^6}$ as a series, but the next number is $2^{\frac{(10^6)+1))}{2}}$-3 or that $2^{10^4}$ is missing or that the values are starting to decrease after that. Can we be absolutely certain that there has to be an algebraic expression to derive this series from? Note that I'm not talking about an infinitely large series, since this is not defined. I am talking about an arbitrary large series with any natural numbers. We need an expression to derive an infitely large series from. Thus, it logically follows that if this assumption (I do assume this is the case) is correct there has to be an inifite number of possible algebraic expressions for all such series. Has this been proven true or false?

A closely related question is whether we know for a fact that there always has to be a polynomial equation for which a given series of natural numbers are the only roots? If this is the case, is this also true for all algebraic numbers?

NidusFormicarum
  • 27
  • Related: https://math.stackexchange.com/questions/1790642/general-formula-for-the-1-5-19-65-211-sequence/1790666#1790666 – Jack D'Aurizio Jan 06 '18 at 18:18
  • "Note that I'm not talking about an infinitely large series, since this is not defined". What do you mean? The sequence of even numbers is infinite, but it's obviously well-defined. – PM 2Ring Jan 06 '18 at 18:19
  • 2
    You need to clarify what you mean by infinite here - your initial example, indexed by $n$, is naturally infinite. – Mark Bennet Jan 06 '18 at 18:19
  • Nope. This is true only after we have defined an expression. The original set was finite. – NidusFormicarum Jan 06 '18 at 18:47

4 Answers4

8

There are uncountably many sequences of natural numbers (as many as real numbers), but only countably many formulas that you can write down.

Therefore, there must be uncountably many sequences of natural numbers that have no explicit formula.

Kenny Lau
  • 25,049
  • 7
    I'm wondering did the OP mean only finite sequences of natural numbers... – Colm Bhandal Jan 06 '18 at 18:15
  • This is essentially what I was about to post when your answer came up. – Mark Bennet Jan 06 '18 at 18:17
  • Yes, I guess "finite set" was a better way to put it. I wrote "arbitrary large", but not infinite. When we have chosen an expression, the set will be contained within the series of numbers we get from the expression. In other words, the numbers will continue although they are not part of the original set. Therefore, more expressions are possible. When we see a partern like "1,3,9,27..." we go aha! the next number is 81. But the next number might well be 5 or any other number. – NidusFormicarum Jan 06 '18 at 18:35
  • @NidusFormicarum Indeed. I think your intuition rings well. As an aside, I recall hearing once a complaint about IQ tests that gave you a sequence of numbers and asked you to guess the next. The complaint was by a mathematician who proved that there are infinitiely many plausible next numbers. The designers of the IQ test responded with a sort of hand-waving Occam's razor answer "We're looking for the simplest solution!" - whatever that means. – Colm Bhandal Jan 06 '18 at 19:19
  • Thank you for your answers! Yes, I have thought about that too. And even more so if we allow for logarithms, sine, factorials, you name it ... This was my first question here so perhaps I should post another one now. The follow up question is whether this is still true if we expand the set to include a given number of arbitrary algrebraic numbers, instead of just integers. – NidusFormicarum Jan 06 '18 at 19:51
7

There is countably many arbitrarily large but finite sequences, and surely there are formulas for each of them. Use the Lagrange interpolation polynomial, for instance.

There are uncountably many infinite sequences, so they cannot be all covered by formulas (written using finitely many different symbols, as we humans do), because there are only countably many such formulas.

5

Concerning your final question (and assuming that by “series” what you mean is “finite set”), the answer is affirmative. If $k_1,\ldots,k_n\in\mathbb N$, then these numbers are the roots of the polynomial$$P(x)=(x-k_1)(x-k_2)\ldots(x-k_n),$$which has no other roots.

And please don't post several questions as a single one.

José Carlos Santos
  • 427,504
4

To avoid overlap with other answers, I'm assuming the following:

  • As an input you're given a finite list of natural numbers- let's say there are $m$ of them in total: $c_1, c_2, \dots, c_m$.
  • You want to write down a closed form expression in one variable, $i$, which is a natural number, that takes on each of the values in this finite list as its first $m$ terms.

Indeed this is possible, and furthermore we can always solve it with a polynomial of degree $m-1$. To show this, first write the polynomial:

$$a_{m-1}i^{m-1} + a_{m-2}i^{m-2} + \dots + a_0$$

Now, plug in the values for $i = 1, 2, 3, \dots, m$, and set the RHS equal to $c_i$, and you'll get a set of simultaneous equations i.e. an $m$ by $m$ matrix which you can solve via linear algebra.

Note: I don't think any of your rows will be linearly dependent, but even if some were, that's not a problem! It just means you can do it with an even lower degree polynomial.

Colm Bhandal
  • 4,649
  • 1
    And indeed, the equations are independent because the determinant of the system is Vandermonde determinant (https://en.wikipedia.org/wiki/Vandermonde_matrix#Vandermonde_determinant) and $1,2,\ldots,m$ are all different from each other. –  Jan 06 '18 at 19:11
  • Ha thanks my intuition told me they should be but I was too lazy to check! – Colm Bhandal Jan 06 '18 at 19:13