# Infinite partial fraction expansions to compute fractional iterations and recurrences

Let say a function $$f$$ is defined iteratively over the set of positive integers, for instance $$f(t+1)=f(f(t))$$ or $$f(t+1)=f(t)+f(t-1)$$. Based on the recurrence relationship and initial conditions, how would you define $$f(t)$$ if $$t$$ is a fraction or an irrational number? In short, you have a function $$f$$ defined over the set of natural numbers, and you try to expand the domain to cover all real numbers, while at the same time making $$f$$ well behaved.

The classic solution is to use Newtonian series, which have been known for centuries, and described briefly in my last section. Here I propose a new approach based on Fourier methods.

My questions are:

• For which functions $$f$$ is my method applicable? Can it be generalized to handle a bigger class of functions?
• Does it produce the same resulting function as the method based on Newtonian series, when both methods are applicable?
• Are there undesirable features attached to my method?

My method

It starts with the following result, which is a direct application of the infinite product formula for the sine function, combined with using L'Hospital rule when $$t=k$$ in the formula below. Many (but not all) functions satisfy

$$f(t) = \frac{\sin\pi t}{\pi}\cdot \Big[\frac{f(0)}{t} +\phi'(t)\sum_{k=1}^\infty (-1)^k \frac{f(k)}{\phi(t)-\phi(k)} \Big]$$

where $$\phi$$ is a well behaved function satisfying $$\phi'(t)\neq 0$$ if $$t$$ is a strictly positive integer. In all my examples I only used $$\phi(t)=t^2$$, thus with $$\phi'(t)=2t$$. So we assume here that $$\phi(t)=t^2$$. In short, my result states (under appropriate convergence conditions) that for many standard even function, if you know $$f(0), f(1), f(2),\dots$$ then you can re-construct or extent $$f(t)$$ to any real number $$t$$ using my formula. Note that for integer values of $$t$$, the value for $$f(t)$$ computed with my formula is in fact a well-defined, implicit limit.

A well known and fundamental example of a function $$f$$ satisfying my above formula is $$f(t)=1$$. Another one is $$f(t)=\cos \lambda t$$ if $$|\lambda|<\pi$$. Obviously, if the formula applies to two functions $$f_1,f_2$$ then it also applies to any linear combination of these two functions.

So my method will work well (that is, my formula applies) for any function $$f$$ that can be written either as

$$f(t)=\sum_{k=0}^\infty \alpha_k \cos \beta_k t, \mbox{ with } |\beta_k|<\pi$$

or

$$f(t)=\int_{-\infty}^\infty w(u)\cos(ut) du$$ where $$w$$ is a weight function with $$w(u)=0$$ if $$|u|\geq\pi$$. That is, it works if $$f$$ is the cosine Fourier transform of a truncated function $$w$$.

A counter-example

Many functions do not satisfy the first formula mentioned in my post. An example is $$f(t)=t^2$$. Yet, surprisingly, my formula offers a pretty good approximation, especially as $$t$$ becomes larger. To avoid confusion, let us denote as $$f^*(t)$$ the partial fraction expansion in my formula, supposed to approximate $$f(t)$$ as closely as possible. In the perfect case described above, we have $$f^*(t) = f(t)$$ for all real numbers $$t$$. In the imperfect case like $$f(t)=t^2$$, we have $$f^*(t) = f(t)$$ only for $$t$$ a positive integer. Below are two charts, the first one comparing $$f(t)$$ with $$f^*(t)$$, the second one displaying the error $$f^*(t)-f(t)$$ when $$f(t)=t^2$$ and $$t\in [0, 5.5]$$.

It is interesting to note that for $$f(t)=\cos 3t$$, the approximation is exact everywhere, while $$f(t)=\cos 4t$$ is one of the worst cases with a large error except if $$t$$ is close to a positive integer.

Method based on Newtonian series

For comparison purposes, I explain here what mathematicians typically use when confronted with this problem. The general formula (instead of my formula based on partial fraction expansions) is:

$$f(t)=\sum_{k=0}^\infty A_k \cdot G_k(t)$$ where $$G_k(t)=0$$ if $$k=0,1,\dots, k-1$$ and $$G_k(k)\neq 0$$. Other than that, the functions $$G_k$$ are arbitrary. The coefficients $$A_k$$ are easily computed iteratively using $$A_k=\frac{1}{G_k(k)} \cdot \Big[f(k)-\sum_{j=0}^{k-1}A_j G_j(k) \Big].$$

The Newtonian series method uses $$G_k(t)=t(t-1)(t-2)\cdots (t-k+1)/k!$$ with $$G_0(t)=1$$, resulting in $$A_k=\sum_{j=0}^k (-1)^{k-j}{k\choose j}f(j).$$

Despite $$f(t)$$ defined that way being an interpolation polynomial of infinite degree, it typically leads to a pretty smooth function.

• I just realized this can be generalized to multidimensional functions whose values are known only on a lattice. It is somewhat related to kriging techniques and can even be generalized if values of $f(s,t)$ are known only at arbitrary (random) locations. It provides a robust, well-conditioned interpolation technique. Nov 10, 2020 at 17:09
• Also wondering how this is connected to wavelets (en.wikipedia.org/wiki/Wavelet). Nov 10, 2020 at 18:27