I am interested in finding a function $\delta(n)$ that solves a functional equation of the form—$$\delta(n) = \delta(2n) + \kappa(n),$$for all integers $n \ge 1$ that are powers of 2, where $\kappa(n)$ is a known function that depends on $n$. This equation came up when seeking answers to a question of mine about converging polynomials. For example (Nacu and Peres 2005, proposition 10):
- If $\kappa(n) = \dfrac C {\sqrt{2n}}$, then $\delta(n) = \dfrac{(1+\sqrt{2})C}{\sqrt{n}}$, where $C > 0$.
- If $\kappa(n) = \dfrac M {4n}$, then $\delta(n) = \dfrac M {2n}$, where $M > 0$.
Unfortunately, I don't know how to solve this functional equation for $\delta(n)$ when $\kappa(n)$ is arbitrary. An example is $\kappa(2^m) = \dfrac M 2 \cdot \dfrac 1 {8\cdot2^m-4}$, which is not a hypergeometric function as rsolve requires. How can I do that?
REFERENCES:
- Nacu, Şerban, and Yuval Peres. "Fast simulation of new coins from old", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
Best Answer
Well, not much can be said about the solutions in the general case where $ \kappa $ is arbitrary. The only useful (and fairly trivial) observation is that using induction, you can show that for each $ n \ge 1 $ that is a power of $ 2 $, you have $$ \delta ( n ) = \delta ( 1 ) - \sum _ { k = 0 } ^ { \log _ 2 ( n ) - 1 } \kappa \left( 2 ^ k \right) \text . \tag 0 \label 0 $$ This shows that given $ \delta ( 1 ) $, $ \delta ( n ) $ is determined uniquely. It very much depends on what $ \kappa $ is whether there is a closed form for $ \delta $ or not.
In the special case that $$ \kappa ( n ) = \frac M { 8 ( 2 n - 1 ) } \tag 1 \label 1 $$ which is of your interest, WolframAlpha gives the solution in terms of the $ q $-digamma function $ \psi _ q $, which is the $ q $-analog of the digamma function $ \psi $. $ \psi _ q ( x ) $ is defined to be equal to $ \frac 1 { \Gamma _ q ( x ) } \frac { \partial \Gamma _ q ( x ) } { \partial x } $, as we similarly had $ \psi ( x ) = \frac 1 { \Gamma ( x ) } \frac { \mathrm d \Gamma ( x ) } { \mathrm d x } $, where $ \Gamma $ is the gamma function, and $ \Gamma _ q $ is its $ q $-analog, the $ q $-gamma function. While these are all well-know functions, their definitions involve sums, and calculating their values may not be much easier than calculating the sum appearing in \eqref{0}. But as they are well-known special functions, any usual computational software has some implementation of them, which may be useful to you.
Anyways, in case of \eqref{1}, the solution given by WolframAlpha can be simplified to the following form: $$ \delta ( n ) = K + \frac M 8 \Big( \log _ 2 ( n ) - \log _ 2 ( e ) \cdot \psi _ 2 \big( 1 + \log _ 2 ( n ) \big) \Big) \text , $$ where $ e $ is Napier's constant and $ K $ is a constant which can be determined from the value of $ \delta ( 1 ) $.