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.

Possible Duplicate:
Polynomial satisfying $p(x)=3^{x}$ for $ x \in \mathbb{N}$

I'm looking for an elementary solution to this question:

There is no polynomial $P$ such that $P(0)=1, P(1)=3, P(2)=9, P(3)=27, \dots$.

share|improve this question

marked as duplicate by Qiaochu Yuan Jun 6 '12 at 16:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
What does "elementary" mean? No complex analysis? No calculus? –  Arturo Magidin Jun 6 '12 at 16:27
    
Yup, exactly, @ArturoMagidin –  Keivan Jun 6 '12 at 16:35
2  
"Exactly." That's like answering "Is it a boy or a girl?" by saying "Yes." But it doesn't matter, as you've gotten an answer that only uses the fact that a polynomial with infinitely many $0$s must be constant $0$. –  Arturo Magidin Jun 6 '12 at 16:36
    
Oh, no calculus. That kills my answer: $p(x) = e^{kx}$ is degree $n$, but $p'(x) = kp(x)$ is degree $n-1$, contradiction. –  Neal Jun 6 '12 at 16:37
1  
Well, I think that's a problem of thinking in another language. The answer would be: No complex analysis and no calculus. Thanks any ways. –  Keivan Jun 6 '12 at 16:40
add comment

2 Answers 2

up vote 13 down vote accepted

Assume $P(X) = a_n X^n + a_{n-1}X^{n-1} +\ldots + a_1 X + a_0$ is a polynomial that satisfies $P(k) = 3^k$ for all natural numbers $k$. Then $P(k+1) - 3P(k) = 0$ for all $k$, so the polynomials $P(X+1)$ and $3P(X)$ are equal. Now compare the highest coefficient.

share|improve this answer
5  
It might be worth pointing out that the reason $P(X+1)=3P(X)$ is that an $n$th degree polynomial is uniquely determined by $n+1$ points, so holding for all natural numbers clearly satisfies that determination. –  Cameron Buie Jun 6 '12 at 16:38
add comment

If $P(x)$ is a polynomial function of degree $d>0$ of $x$, then the differences $(\Delta P)(x)=P(x+1)-P(x)$ give a polynomial function of degree $d-1$ of $x$ (this follows for polynomials of one term, by the binomial formula, an the general case follows easily from this). You want a nonzero polynomial that satisfies $\Delta P=2P$, but the left hand side has degree one less than the righ hand side, so this is impossible.

This argument (as does the answer by marlu) does use the fact that a polynomial function, even restricted to its values at natural numbers, determines the underlying polynomial uniquely; otherwise the notion of degree (or leading term) of such a function would not be well defined. Note that over finite fields exponential functions are polynomial functions, in many differnt ways. I think it would be rather harder to give an argument not using the mentioned fact.

share|improve this answer
add comment

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