The functional equation $\delta(n) = \delta(2n) + \kappa(n)$

Question

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.

Answer 1

If $\kappa(2^m)$ is a sum of hypergeometric functions, the functional equation in my question has to be converted to a linear recurrence of the form—$$\eta(m) = \eta(m+1) + \kappa(2^m), $$ and the solutions found correspond to those in the original functional equation.

Here is an example in SymPy:

In [250]: rsolve(Eq(f(n), f(n+1) + z/sqrt(2*2**n)), f(n)).simplify()                                                                                                   
Out[250]: 
 -n  ⎛ n              ⎞
 ─── ⎜ ─              ⎟
  2  ⎜ 2              ⎟
2   ⋅⎝2 ⋅C₀ + z + √2⋅z⎠

In [251]: rsolve(Eq(f(n), f(n+1) + z/(4*2**n)), f(n)).simplify()                                                                                                       
Out[251]: 
      -n  
     2  ⋅z
C₀ + ─────
       2  

---

EDIT:

As I found out, this works only if $\kappa(2^m)$ is a sum of hypergeometric functions, not necessarily for more general functions. Thus, my question remains open.

---

EDIT (Apr. 2):

In the meantime, I have managed to settle this question.

For the equation $\delta(n) = \delta(2n) + \kappa(n)$, it's enough to sum $\delta(n) = \kappa(n) + \kappa(2n) + \kappa(4n) + ...$ to get the solution. For this solution, it doesn't matter what the initial $c_1$ is; all that matters is whether the sum converges. I can assume that the sum does converge, and in that case, that sum is the solution I need.

Answer 2

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

Answer 3

As

$$ \delta\left(2^{\log_2 n}\right)=\delta\left(2^{\log_2 (2n)}\right)+\kappa(n) $$

making $d(\cdot)=\delta\left(2^{(\cdot)}\right)$ and $z=\log_2 n$ we have the recurrence

$$ d(z)=d(z+1)+\kappa\left(2^z\right) $$

This recurrence has the solution

$$ d(z) = c_1 -\sum_{i=0}^{z-1}\kappa\left(2^i\right) $$

and going backwards we arrive to

$$ \delta(n) = c_1 - \sum_{i=0}^{\log_2 n -1}\kappa\left(2^i\right) $$

now choosing $\kappa(n) = \frac{c_0}{\sqrt{2n}}$ we have

$$ \delta(n) = c_1-\frac{\left(1+\sqrt{2}\right)\left(\sqrt{n}-1\right)}{\sqrt{n}}c_0 $$

and for $\kappa(n) = \frac{M}{4n}$ then

$$ \delta(n) = c_1-\frac{M (n-1)}{2 n} $$

and finally for $\kappa(n) = \frac{M}{2}\frac{1}{8n-4}$ ...