Is it feasible to transform a polynomial right into a reappearance relationship? If so, just how?

I have actually been attempting to do this for a long time, yet usually talking the partly pertinent details I can locate on the net just managed the inquiry : "How does on transform a reappearance relationship right into ... well, a non - reappearance relation?"

Let is start of with a straightforward instance : $f(n) = 34n^3+51n^2+27n+5$. Just how do we locate $f_{n}$? I 'd actually such as to see this addressed in example with the adhering to : Consider $g(n)=n^6$ We can after that locate the recursion formula : $g_n=((g_{n-1})^{1/6}+1)^6$. What concerning $f_{n}$?

We can generalise this inquiry in a variety of means. As an example, is it (additionally) feasible also transform a boundless polynomial, like the Taylor Series development of a trigonometric formula, right into a recursion formula? In addition, what takes place when we permit the coefficients of the polynomial to be actual and also also facility?

Many thanks,


Bonus side - inquiry : How, if in all, are "generating functions" valuable in this context?

2019-12-02 02:49:58
Source Share
Answers: 4

Any polynomial $f(n)$ of level $d$, over an approximate commutative ring, pleases the recursion

$$\sum_{k=0}^{d+1} (-1)^{d+1-k} {d+1 \choose k} f(x+k) = 0$$

for any kind of $x$. This is an application of the method of finite differences. In regards to generating functions, it claims that

$$\sum_{n \ge 0} f(n) x^n = \frac{P(x)}{(1 - x)^{d+1}}$$

for some polynomial $P(x)$. This need to be extensively covered in a publication like Wilf is generatingfunctionology ; or else, I review it in my notes on generating functions. Extra usually, if $f(n)$ has a creating function of the kind $\frac{P(x)}{Q(x)}$ where $P$ is a polynomial, after that the coefficients of $Q$ define a reappearance that $f(n)$ at some point pleases.

I'm not exactly sure I recognize your even more basic inquiry. Do you have a details application in mind?

2019-12-03 04:20:12

Expand $f(n+1)$ and also 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$.

2019-12-03 04:20:05

Max, I'm simply describing Qiaochu is solution, making use of Pari/GP. First specify the function
$ f(x) = 34*x^3+51*x^2+27*x+5$

Then the first suggestion to decay f right into a 2 - term - recursion is
$ f(x)-1*f(x-1) $
Pari/GP : $ <out> = 102*x^2 + 10 $

So the outcome is currently a lowered polynomial. Currently subtract from this $f(x-1)-f(x-2) $ due to the fact that this will certainly be a polynomial of the very same level, just "shifted" by some coefficients.

This offers
$ f(x)-2*f(x-1)+f(x-2) $
Pari/GP : $ <out> = 204*x - 102 $

Again the resulting polynomial is of lowered order. Currently we end up by deducting $ 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 just. We are ended up and also write, reordering the terms :

$ f(x) = 3*f(x-1)-3*f(x-2)+f(x-3)+204 $

[upgrade ] For efficiency one can increase the level. According to Qiaochu is answer/comment we can subtract once more the x - 1 - changed polynomial $ f(x-1)-3*f(x-2)+3*f(x-3)-f(x-4) $ and also certainly obtaining

$ f(x)-4*f(x-1)+6*f(x-2)-4*f(x-3)+f(x-4) $
Pari/GP : $ <out> = 0 $

finishing the solution $ f(x) = 4*f(x-1)-6*f(x-2)+4*f(x-3)-f(x-4) $

[end upgrade ]

2019-12-03 04:17:56

HINT $\rm\ \ \Delta\ f \ :=\ f(n+1) - f(n)\ $ lowers $\rm\ d = deg\ f\:,\ $ so $\rm\ \Delta^{d+1}\ f\ =\ 0\ $ returns a reappearance for $\rm\: f\:$. Functions confessing reappearances are called P - recursive . Google holonomic function to learn more about their abundant concept - which has prevalent applications.

2019-12-03 01:27:50