Let $p(x)$ be a polynomial with integer coefficients, which is not constant. Then is this condition possible: $$p(x)=3^{x}$$ whenever $x \in \mathbb{N}$.
Polynomial satisfying $p(x)=3^{x}$ for $ x \in \mathbb{N}$
-
13@muad: We expect good calculus students to know that polynomials grow more slowly than exponentials. Certainly we expect this of math grad students. So it looks like a not very well thought out question. – 2010-10-05
-
0@Pete: the algebraic interpretation of the problem is more interesting and the tags now reflect this aspect of the question, in addition to your reclassification as [calculus]. – 2010-10-05
-
1@T..: yes, it is more interesting to interpret the question as taking place in some unspoken ring. Much more interesting: it goes from trivial to nontrivial. I myself didn't (and still don't) read the question this way, but you are of course entitled to construe it as you see fit, especially if it makes for a more interesting question. – 2010-10-05
-
3@T..: or, to put it another way: I like your answer a lot, but it doesn't make me like the question any more than I did before. – 2010-10-05
-
0@Pete: I have no idea what the intended interpretation of the question was, but does it matter? Once a question is posted, it's a sort of mutable "community property" rather than the personal domain of the asker, and the original intentions are less important. We get lucky in this case in that there is something interesting to analyze, for other cases there are downvotes etc. – 2010-10-05
-
0@Pete L. Clark,It's just beacuse there are 11 answers to this question - it's definitely something people find interesting - that's why I was confused there was so few upvotes. It's not something bothering me, I was just finding it odd. – 2010-10-05
-
0@Pete L.Clark: Pete, does MATH.SE always expect a well thought question. Expecting is just expecting and need not be a necessity always. As far as this question is concerned, i didn't know how to solve it, and thats why i posed here. What does it have to do with a grad student? Intensity of Grad students differs in many parts of the world. For many people here, i may appear stupid, but what to do! – 2010-10-05
-
1@Chandru1, you *definitely* don't appear stupid, for once I was happy that I could actually solve one the problems you post :P - just missing something easy is no big deal, I just spent 2 days trying to prove a trivial theorem I thought up in bed (didn't realize it was trivial until the end).. – 2010-10-05
-
6This is becoming a meta-y discussion, so I will risk just one last comment. I'm not accusing anyone of being stupid. Rather, I'm advising a not stupid math graduate student to think a little more (and perhaps others to help out this student's learning process by giving hints rather than specific answers for questions which are definitely within his ability to solve). – 2010-10-05
-
1@Pete.L. Clark: Apologies for misunderstanding your previous quotation – 2010-10-06
10 Answers
Suppose that $p(x)$ exists and has degree $n$. $\lim_{x\to\infty}\frac{p(x)}{x^{n+1}}=0$ and $\lim_{x\to\infty}\frac{3^x}{x^{n+1}}\to\infty$, but $\frac{p(x)}{x^{n+1}}=\frac{3^x}{x^{n+1}}$ for all $x\in\mathbb{N}$, so it is impossible for the first limit to be finite and the second limit to be unbounded.
No, a polynomial can't grow exponentially as $x\to\infty$.
-
1I would like to see a proof – 2010-10-04
-
6+1: $P(x) = o(3^x)$. The integer coefficients etc is a red-herring. – 2010-10-04
-
3@Chandru1: show that $\lim_{x\to\infty}p(x)/3^x=0$ for all polynomials $p$, by induction on the degree of $p$, using, for example, l'Hôpital's rule to do the inductive step. – 2010-10-04
Yet another proof: if $p$ is a nonzero polynomial with real coefficients then $$\lim_{n\to\infty}\frac{p(n+1)}{p(n)}=1$$ which certainly doesn't hold for $p(x)=3^x$.
A polynomial of degree $n$ has the property that $p(x+1) - p(x)$ is a polynomial of degree $n-1$. After taking $n$ finite differences you reach a contradiction.
-
0This one, I like for simplicity. – 2010-10-04
-
0Well, after taking N finite differences (in this problem) you get 2^N=0. This could be a contradiction or not depending on what other assumptions are made. – 2010-10-05
$\rm\ p(x) = 3^x\:$ on $\rm\:\mathbb N\ \Rightarrow\ p(2x) = p(x)^2\:$ on $\rm\:\mathbb N \ \Rightarrow\ p(2x) = p(x)^2\:$ contra degree comparison.
-
0This is one of the prettiest. – 2010-10-05
-
0You also need the fact that p isn't constant :-) – 2010-10-07
-
2@yatima2975: Of course, proof sketches often omit obvious routine inferences so to focus on the essence. – 2010-10-07
-
4What can I say? I'm a stickler for details! – 2010-10-09
The answer depends on the ring (which the question did not specify) where $x$ and $p(x)$ take their values. Polynomials with integer coefficients, and non-negative powers of integers such as $3^n$, can be evaluated in any ring, so the question makes sense in this generality.
In a ring where 2=0 (such as the integers modulo 2), $3^n = 1^n$, and any polynomial with $p(0)=p(1)=1$ is an example. It should be an interesting problem to determine all rings where there is such a $p(x)$.
ADDED: Let's consider the situation over an arbitrary commutative ring $R$ with unit. $Q(x) = p(x+1)- 3p(x)$ is zero (as a function) for all $x$ in the image of $\mathbb{Z}$ in $R$. If $R$ is of characteristic different from $2$, $\deg Q = \deg P$ (as polynomials). In characteristic 0 having zeros at all integers is enough to force $Q = 0$ as a polynomial, and there are no examples. In finite characteristic $n > 1$, we also have $p(n) = 3^n = p(0) = 1$ so that $n | (3^n - 1)$. If $n$ is prime then $n | (3^n - 3)$ so that $n | 2$ and thus $n=2$. If $n$ is not prime, and $q$ is a prime dividing $n$, then an example in $R$ is an example in $R/q$ which has prime characteristic $q$ and therefore $q=2$. So the only remaining possibility is a ring where $2^k = 0$, for $k > 1$. For such rings there are examples because in the binomial expansion of $(1+2)^n = 1 + 2n + 2n(n-1) + 4n(n-1)(n-2)/3 + 2n(n-1)(n-2)(n-3)/3 + \dots$ all terms are congruent modulo $2^k$ to polynomials with integer coefficients, and all terms of degree higher than $2^k - 1$ vanish on the integers modulo $2^k$.
ADDED-2: one can see that $2^k=0$ more directly by writing $p(n+1)-p(n) = 2p(n)$ (for images of integer $n$ in our ring). This means that $\Delta^k p(n) = 2^k p(n)$ and for $k > deg(P)$ this will be zero, then set $n=0$ to get $0 = 2^k p(0)= 2^k$. [Note that this argument applies to $p(n)$ for integer $n$ only, not $p(x)$ as an abstract polynomial or a polynomial evaluated at non-integer values of $x$.]
Conclusion: there are polynomials $p(x)$ such that $p(n)=3^n$ for all $n \geq 0$ (with the polynomial considered as a function on the commutative ring-with-unit $R$) if and only if in this ring, $2^k = 0$ for some positive integer $k$.
$\rm\ p(x+1) = 3\:p(x)\:$ on $\rm\:\mathbb N\ \Rightarrow\ p(x+1) = 3\:p(x)\ \Rightarrow\ p(-1) = 1/3\ $ contra $\rm\ p(x)\in \mathbb Z[x]\:$.
Or, continuing, $\rm\ p(-n) = 3^{-n}\: \Rightarrow \ p(x)\:p(-x) = 1\:$ on $\rm\:\mathbb N\ \Rightarrow\ p(-x)\:p(x) = 1\ $ contra degree comparison. This proof works over much more general coefficient rings, e.g. $\mathbb Q\:$.
Suppose $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 = 3^x$ for $x \in \mathbb N$.
Then $a_n (x+1)^n + a_{n-1} (x+1)^{n-1} + \cdots + a_0 = 3 a_n x^n + 3 a_{n-1} x^{n-1} + \cdots + 3 a_0$.
But the coefficient of $x^n$ on the LHS is $a_n$ and on the RHS it is $3 a_n$.
This contradicts the assumption.
-
6You want to assume that $a_n\neq0$ somewhere :) – 2010-10-04
-
0I don't make that assumption. – 2010-10-04
-
0@muad: then you haven't reached a contradiction. – 2010-10-04
-
0@Qiaochu Yuan - The argument shows that all coefficients must be 0 but the constant coefficient is 1 (base case of the induction is not written because it is trivial - infact it's not even induction, just case analysis $0$ or $x+1$). – 2010-10-04
If so then then the values of $\rm\: q(x) = p(x^2)\:$ are all powers of 3, contradicting the fact that infinitely many primes must occur among the values of a nonconstant $\rm\: p(x) \in \mathbb Z[x]\:$, by way of a simple Euclid-like proof.
Here's another argument (at the other end of the real line!):
Such a polynomial would have to be non-constant, which means that it tends to $\infty$ or $-\infty$ as $x\to-\infty$. But this is impossible, since $3^x \to 0$ as $x\to-\infty$.
-
3Oops, sorry. The question said $x\in\mathbb{N}$, not $x\in\mathbb{Z}$ as I thought for a moment. Well, never mind, I'll leave the answer here anyway, since it shows that a polynomial cannot *decay* exponentially either... – 2010-10-04