Infinite recurrence relation which depends on subsequent sequence values

Question

I'm trying to solve a problem and I have it reduced to solving the following recurrence relation which goes "backwards" as the value of $p_i$ depends on subsequent values.

$p_i\in [0,1]$

$p_i = 0 (i < 7) $

$p_i = {1\over 2} p_{i-7+1} + {1\over 4} p_{i-7+2} + {1\over 8} p_{i-7+4} + {1\over 16} p_{i-7+8} + {1\over 32} p_{i-7+16} + ... (i>=7)$

which I rewrote as

$p_{i+1} = 2p_{i+7} - {1 \over 2}p_{i+2} - {1 \over 4}p_{i+4} - {1 \over 8}p_{i+8} - {1 \over 16}p_{i+16} - {1 \over 32}p_{i+32}...$

Note that we know

$\lim_{i \to \infty } p_i = 1$

Is there any way to solve this? I thought about using characteristic equations as used to find closed form for say, fibonacci numbers, but it doesn't seem to work here as it's an infinite series. I tried reducing it via some sort of telescopic operation but I got nowhere. Could it be solved with generating functions? Or something else?

Answer 1

Note

The numerical results in the older version of this answer is completely WRONG. The CAS I use (maxima) becomes numerically unstable when one raise a complex number to a high power directly. What a shame!

Following is a complete rewrite which hopefully fix all the problem. The methodology remains essentially the same. However, don't trust the numbers I posted here, please regenerate them yourself with any CAS other than maxima.

---

If one ignore the initial conditions $p_k = 0$ for $k = 1,\ldots, 6$, there are solutions to the recurrence relation in the form $p_k = \lambda^k$ where $\lambda$ is any root of following function $g(\lambda)$ within the closed unit disk $|\lambda| \le 1$. $$g(\lambda) \stackrel{def}{=} \lambda^6 - \sum_{k=0}^\infty \frac{\lambda^{2^k-1}}{2^{k+1}}$$

It is easy to check $\lambda = 1$ is the only root on the boundary $|\lambda| = 1$.

If one plot $g(\lambda)$ along the circle $|\lambda| = 1 - \epsilon\;$ for some small positive $\epsilon$, say $\epsilon \approx 0.01$, its image will wraps around the origin $5$ times. This means counting multiplicity, $g(\lambda) = 0$ has $5$ roots in the open disk $|\lambda| < 1-\epsilon$.

There is actually one more root of $g(\lambda)$ hiding near the trivial root $1$. If one plot $g(e^{i\theta})$ for $|\theta| < 0.0001$, one discover $g(e^{i\theta})$ wraps around the origin one extra time for very small $\theta$!

To summarize, $g(\lambda)$ has $6$ roots within the open unit disk. Two real and two complex conjugate pairs. Let $\alpha, \gamma$ be the two real roots and $\beta, \bar{\beta}$; $\gamma, \bar{\gamma}$ be the two complex conjugate pairs. Numerically, they are located roughly at

$$\begin{cases} \alpha &= +0.9998676723626686\\ \beta &= +0.4001321085786921 + 0.811461115981079i\\ \gamma &= -0.5024718402727043 + 0.732127339291527i\\ \delta &= -0.7837246138810408 \end{cases}$$

The recurrence relation has solutions of the form

$$p_k = K - A \alpha^k - 2\Re\left[ B \beta^k + C \gamma^ k \right] - D \delta^k$$

where $K, A, D$ are real and $B, C$ are complex constants.

Since we want $\lim_{k\to\infty} p_k = 1$, we need to set $K$ to $1$. We are left with $2$ real parameter $A, D$ and $2$ complex parameters $B, C$. This is equivalent to $6$ real parameters and enough free parameters for us to fulfill the initial condition $p_k = 0$ for $k = 1,\ldots 6$.

Let $P(x)$ and $Q(x)$ be the functions defined by: $$\begin{cases} P(x) &= (x - \alpha)(x - \beta)(x-\bar{\beta})(x-\gamma)(x-\bar{\gamma})(x-\delta)\\ Q(x) &= \frac{P(1)}{x(1-x)P'(x)} \end{cases} $$ In terms of $Q(\cdot)$, the coefficients we seek are given by

$$\begin{cases} A &= Q(\alpha) \approx 1.000504902182149\\ B &= Q(\beta) \approx ( 1.597779223823348 + 1.084728069034189 i) \times 10^{-4}\\ C &= Q(\gamma) \approx ( 1.452671463695825 + 0.08052243089845321 i) \times 10^{-4}\\ D &= Q(\delta) \approx 2.125153629768949 \times 10^{-4} \end{cases} $$ Please note that aside from $A$, the coefficient associated with the largest root $\alpha$, all other coefficients are of the order $10^{-4}$ and falls off much faster. For large $n$, $p_n$ behaves like $1 - A \alpha^n$.

Once again, this is more or less a proof of existence. I have no idea how to justify the solution constructed this way is the only solution.

Answer 2

Let $f(x)= \sum_{i=0} p_i x^i$ and $g(x) = x^7 - \sum_{i \ge 0} x^{2^i} 2^{-1-i}$.

$f$ has radius of convergence exactly $1$ and $g$ has radius of convergence $2$. If I am not mistaken, your relations says that $f(1/x)g(x)$, that converges for $1<|x|<2$, is actually a power series in $x$.

Hence it has radius of converge at least $2$, And this shows that $f$ has a meromorphic continuation on the whole Riemann sphere, so it is a rational fraction.

Moreover, it has no poles of modulus less than $1$, and so its poles have to be inverses of the zeros of $g$ of modulus less than $1$.

This should complete the answer above, and if the solution is unique you should be able to show it from there.

---

Edit : Uniqueness was in fact easy :

Suppose you have 2 solutions $p$ and $q$. Since $p-q$ satisfies the recurrence relations, is zero on the first six terms and converges to zero, it has to be zero :

Suppose it has an element with maximal modulus. Since it can't be one of the first six terms, the recurrence relation says that it is a weighted average of some other terms. Then all those terms have to be equal, and so the sequence can't converge to zero, contradiction.