Is it possible to convert a polynomial into a recurrence relation? If so, how? I have been trying to do this for quite a while, but generally speaking the partially relevant information I could find on the internet only dealt with the question: "How does on convert a recurrence relation into... well, a non-recurrence relation?" 
Let's start of with a simple example: $f(n) = 34n^3+51n^2+27n+5$. How do we find $f_{n}$? 
I'd really like to see this solved in analogy with the following: Consider $g(n)=n^6$ We can then find the recursion formula: $g_n=((g_{n-1})^{1/6}+1)^6$. What about $f_{n}$?
We could generalize this question in a number of ways. For instance, is it (also) possible too turn an infinite polynomial, like the Taylor Series expansion of a trigonometric formula, into a recursion formula? Furthermore, what happens when we allow the coefficients of the polynomial to be real and even complex?
Thanks,
Max
Bonus side-question: How, if at all, are "generating functions" useful in this context?
 A: Max, I'm just detailing Qiaochu's answer, using Pari/GP.
First define the function
$ f(x) = 34*x^3+51*x^2+27*x+5$    
Then the first idea to decompose f into a 2-term-recursion is
$ f(x)-1*f(x-1) $
Pari/GP: $ <out> = 102*x^2 + 10 $    
So the result is already a reduced polynomial. Now subtract from this $f(x-1)-f(x-2) $ because this will be a polynomial of the same degree, only "shifted" by some coefficients.   
This gives
$ f(x)-2*f(x-1)+f(x-2) $
Pari/GP: $ <out>  = 204*x - 102 $    
Again the resulting polynomial is of reduced order. Now we finish by subtracting $ f(x-1)-2*f(x-2)+f(x-3) $     
We get:
$ f(x)-3*f(x-1)+3*f(x-2)-f(x-3) $
Pari/GP: $ <out> = 204 $     
Now we have a constant expression only. We are finished and write, reordering the terms:   
$ f(x) = 3*f(x-1)-3*f(x-2)+f(x-3)+204 $    
[update] For completeness one can increase the degree. According to Qiaochu's answer/comment we can subtract again the x-1-shifted polynomial $ f(x-1)-3*f(x-2)+3*f(x-3)-f(x-4) $ and of course getting    
$ f(x)-4*f(x-1)+6*f(x-2)-4*f(x-3)+f(x-4) $
Pari/GP: $ <out> = 0 $     
completing the answer 
$ f(x) = 4*f(x-1)-6*f(x-2)+4*f(x-3)-f(x-4) $    
[end update]
A: Expand $f(n+1)$ and you'll get $f(n+1)=f(n)+g(n)$ for some $g$. For $f(n)=34n^3+51n^2+27n+5$, you get $f(n+1)=f(n)+102n^2+204n+112$. 
A: Any polynomial $f(n)$ of degree $d$, over an arbitrary commutative ring, satisfies the recursion
$$\sum_{k=0}^{d+1} (-1)^{d+1-k} {d+1 \choose k} f(x+k) = 0$$
for any $x$.  This is an application of the method of finite differences.  In terms of generating functions, it says that
$$\sum_{n \ge 0} f(n) x^n = \frac{P(x)}{(1 - x)^{d+1}}$$
for some polynomial $P(x)$.  This should be thoroughly covered in a book like Wilf's generatingfunctionology; otherwise, I discuss it in my notes on generating functions.  More generally, if $f(n)$ has a generating function of the form $\frac{P(x)}{Q(x)}$ where $P$ is a polynomial, then the coefficients of $Q$ describe a recurrence that $f(n)$ eventually satisfies.
I'm not sure I understand your more general question.  Do you have a specific application in mind?  
A: HINT $\rm\ \ \Delta\ f \ :=\ f(n+1) - f(n)\ $ reduces $\rm\ d = deg\ f\:,\ $ so $\rm\ \Delta^{d+1}\ f\ =\ 0\ $ yields a recurrence for $\rm\: f\:$. Functions admitting recurrences are known as P-recursive. Google holonomic function to learn about their rich theory - which has widespread applications.
