Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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? –  jvargas Jul 21 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 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 at 15:40
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). –  user61527 Jul 21 at 15:43
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. –  user61527 Jul 21 at 15:44

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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 at 15:49
    
Point well made. –  jvargas Jul 21 at 15:56
1  
@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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.