# Why can't a polynomial fit infinitely many points of an exponential function? [duplicate]

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

-

## marked as duplicate by Qiaochu YuanJun 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.

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
"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
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

## 2 Answers

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.

-
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

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.

-