# Prove that no polynomial function represents a given sequence

I recently encountered the following question:

How to find the $n$th term of the sequence $2,3,6,7,14,15,30,\dots$?

I replied to that post, and gave the following answer: $S_n = {2}^{\lceil\frac{n}{2}\rceil}+2(\frac{n}{2}-\lfloor\frac{n}{2}\rfloor-1)$

As part of the the question, OP noted that every element was equal either to the previous element times $2$ or to the previous element plus $1$. But if he/she hadn't done so, then I could have just as well used Lagrange Polynomial Interpolation in order to provide the following answer:

$\displaystyle\frac{7x^6}{60}-\frac{163x^5}{60}+\frac{299x^4}{12}-\frac{1369x^3}{12}+\frac{8159x^2}{30}-\frac{1566x}{5}+135$

Now I would like to ask the "sort of opposite" question:

Can we prove that there is no polynomial solution for the original problem?

In other words, can we prove that no polynomial $P(x)$ exists, such that $\forall{n}\in\mathbb{N}:P(n)=S_n$?

-
To do so you need an infinite sequence, otherwise you will always be able to find such a polynomial using interpolation. Is $S_n$ infinite? And, do we know all the terms? – ReverseFlow Jul 21 '14 at 15:38
@T.Bongers: Did you read the "OP noted that every element was equal either to the previous element times 2 or to the previous element plus 1" part of my question? – barak manos Jul 21 '14 at 15:38
@T.Bongers: In any case, my question is not about the sequence given in the original question that I've encountered, but about whether or not it can be proved that no polynomial $P(x)$ exists, such that $P(n)=S_n$, where $S_n$ is not the sequence that was given in the original question, but the sequence that I gave as an answer (also specified at the beginning of this question). – barak manos Jul 21 '14 at 15:40
In that case, you may wish to clarify the question as something like: Define a sequence $S_n$ by this particular rule involving doubling previous terms. Can we prove there is no polynomial such that.... (rather than defining the sequence in terms of its first seven terms, which has apparently confused at least me and one other). – user61527 Jul 21 '14 at 15:43
Regardless, to answer your question: The odd-index terms are essentially doubling at every step, so we can get a lower bound of something like $$2^k \lesssim S_{2k + 1}$$ so that $S$ grows faster than any polynomial. – user61527 Jul 21 '14 at 15:44

Sure. Note that $\lim_{n \to \infty} \frac{P(n+1)}{P(n)} = 1$ for any (non-zero) polynomial $P$, whereas $\limsup_{n \to \infty}\frac{S_{n+1}}{S_n} = 2$.

-
Do you mean that $\displaystyle\lim_{n\to\infty}\frac{S_{2n+1}}{S_{2n}}=2$? Because $\displaystyle\lim_{n\to\infty}\frac{S_{n+1}}{S_{n}}$ goes between $1$ and $2$. – barak manos Jul 21 '14 at 15:49
Point well made. – ReverseFlow Jul 21 '14 at 15:56
@barakmanos on the contrary: I mean that the limit superior of the sequence $S_{n+1}/S_n$ is $2$. As you point out though, you could just as easily talk about the sequence $S_{2n+1}/S_{2n}$ – Omnomnomnom Jul 21 '14 at 16:06

Your sequence $S_n$ has the property that for $n$ large, $$S_n > \frac{\sqrt{2}^n}{2}.$$ Suppose that $f$ is a polynomial of degree $p$ with $f(n) = S_n$. Then you'd have $$c n^p > \sqrt{2}^n$$ for some constant $c$ (the leading coefficient of $f$, a factor of 2, ...) and all sufficiently large $n$. Taking logs, that becomes $$\log(c) + p \log(n) > \frac{n}{2} \log(2)$$ But $\log$ defintely grows slower than $n$, so this is a contradiction.

Short form: your sequence behaves exponentially; polynomials don't.

-