5
$\begingroup$

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?

  • 0
    $f(n+1) = g(n) + f(n)$. Is that recursive enough? Do you have anything specific in mind?2010-12-08
  • 0
    @ 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.2010-12-08
  • 0
    @ Moron: I've added some text to the question, perhaps that clarifies it?2010-12-08
  • 0
    @ Moron: aah I've got it, I confused 'recursion formula' with 'recurrence relation'!2010-12-08
  • 0
    @Max: I believe Qiaochu's answer gives you a linear recurrence, where the coefficients depend only on the degree.2010-12-08
  • 0
    Hmm, after re-reading your edited question: is it right that you search for something like indefinite sum-term?2010-12-08
  • 0
    $f(n) = 34n^3+51n^2+27n+5 = 5, 117, 535, 1463, 3105, 5665,\dots$ is the [sequence](https://oeis.org/A006221) from Apery's cfrac for $\zeta(3)$. No wonder the polynomial $f(n)$ looked familiar. (Whatever will we do without the OEIS?)2015-08-10

4 Answers 4

14

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?

  • 0
    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.2010-12-08
  • 0
    I've added some text to the question to clarify what I have in mind considering the simpel case.2010-12-08
  • 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.2010-12-08
  • 0
    @ 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$ !)2010-12-08
  • 0
    Oh allright then clearly there are some things I don't understand very well yet, thank you.2010-12-08
  • 0
    @Max: what is the difference between "recursion formulas" and "recurrence relations"?2010-12-08
  • 0
    @ Qioachu: "recurrence relation" has a Wikipedia article and "recursion formula(s)" hasn't (recursion does, though). Joking, but it's true.2010-12-08
  • 2
    @Max: as far as I can tell, they should mean the same thing.2010-12-08
  • 0
    @Qiaochu: Ok. (Some extra text to make a comment)2010-12-08
  • 0
    Hi @QiaochuYuan unfortunately the link to your notes on generating functions is broken, would you be so kind to provide a new one? I am looking to find a recurrence relation similar to the one of Legendre polynomials for any set of Polynomial basis functions. Do you know of something like that?2018-01-12
3

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: $ = 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: $ = 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: $ = 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: $ = 0 $

completing the answer $ f(x) = 4*f(x-1)-6*f(x-2)+4*f(x-3)-f(x-4) $

[end update]

2

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

  • 0
    Ok but how do I express $f_n$ then? (See par. 2 of the question).2010-12-08
  • 0
    @ lhf: I'm sorry, I made an error in my question. I took "recursion formula" for recurrence relation...2010-12-08
1

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.