0

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$?

Community
  • 1
barak manos
  • 43,109
  • 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? – ReverseFlowControl 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
  • @Genomeme: Please read my comment to T.Bongers above. My question relates to the infinite sequence $S_n$, as stated at the beginning (3rd line from the top). – barak manos Jul 21 '14 at 15:43
  • 1
    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). –  Jul 21 '14 at 15:43
  • @T.Bongers: I ask a question about $S_n$, where $S_n$ is depicted/stated/described/written at the beginning of that question. – barak manos Jul 21 '14 at 15:44
  • 2
    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. –  Jul 21 '14 at 15:44
  • @T.Bongers: Thanks, that's starting to look more like an accurate answer to my question :) ... Though I think I should have probably used some other sequence, as my purpose behind the scene was to refer to the floor aspect of the sequence and not to its exponential growth. – barak manos Jul 21 '14 at 15:46

2 Answers2

5

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$.

Ben Grossmann
  • 225,327
1

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.

John Hughes
  • 93,729