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.

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?

share|improve this question
    
$f(n+1) = g(n) + f(n)$. Is that recursive enough? Do you have anything specific in mind? –  Aryabhata Dec 8 '10 at 20:02
    
@ Moron: I was thinking of something like the closed-form non-recursive function for the n-th Fibonacci number, derived from the recursion formula $f_n=f_{n-1} + f_{n-2}$. We could find $f(n)=\frac{\phi^n -(1-\phi)^n}{\sqrt{5}}$. Only this time, I want to go the other way around and do this with the polynomial I mentioned. –  Max Muller Dec 8 '10 at 20:08
    
@ Moron: I've added some text to the question, perhaps that clarifies it? –  Max Muller Dec 8 '10 at 20:34
    
@ Moron: aah I've got it, I confused 'recursion formula' with 'recurrence relation'! –  Max Muller Dec 8 '10 at 20:46
    
@Max: I believe Qiaochu's answer gives you a linear recurrence, where the coefficients depend only on the degree. –  Aryabhata Dec 8 '10 at 20:49
show 1 more comment

4 Answers

up vote 13 down vote accepted

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?

share|improve this answer
    
Thank you. I'm not entirely sure how to use this information to express the recursion formula of f(n) now, though. If $f(n)=34n^3+51n^2+27n+5$, then $f_n=...$? (And now some expression involving $a \cdot f_{n-1} +/- ...$ comes on the dots. To illustrate my more general question: say we have $g(x) = sin(x)$. Then the corresponding Taylor series is $x-x^3/3! + x^5/5!...$ How do we express $g_x$, then? I don't have a specific application in mind, just curious. –  Max Muller Dec 8 '10 at 20:20
    
I've added some text to the question to clarify what I have in mind considering the simpel case. –  Max Muller Dec 8 '10 at 20:31
1  
f_n = 4f_{n-1} - 6f_{n-2} + 4f_{n-3} - f_{n-4}. This is the d = 3 case of the identity I gave. I don't think there's anything meaningful you can say about the general question. For the particular case of sin you can use the angle addition formula, I guess. –  Qiaochu Yuan Dec 8 '10 at 20:47
    
@ Qiaochu: please re-read the title of the question, I mistook "recursion formula" for "recurrence relation". I am most interested in the question in its non-general form: how does one find recurrence relationships for polynomials, especially considering f(x)? I do have an application for this in mind, which I will show you in my next question (if one of you can find $f_n$ !) –  Max Muller Dec 8 '10 at 20:50
2  
@Max: as far as I can tell, they should mean the same thing. –  Qiaochu Yuan Dec 8 '10 at 21:05
show 4 more comments

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]

share|improve this answer
add comment

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

share|improve this answer
    
Ok but how do I express $f_n$ then? (See par. 2 of the question). –  Max Muller Dec 8 '10 at 20:40
    
@ lhf: I'm sorry, I made an error in my question. I took "recursion formula" for recurrence relation... –  Max Muller Dec 8 '10 at 20:47
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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