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