3
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ I redo my calculation today and I notice the CAS I use is producing some garbage numbers in the middle of the process. Even though I think the methodology I use before is okay, I'm no longer sure about the conclusion. I'll delete my answer until I'm able to fix it and recheck the numbers. $\endgroup$ Dec 21, 2015 at 7:06
  • $\begingroup$ I complete rewrite the answer. I hope this fix all the problems. $\endgroup$ Dec 21, 2015 at 14:21

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for this, although I don't understand 100% what you did. Where did the numeric values for $\alpha$, $\beta$, $\gamma$ come from? Are these located uniformly around the unit circle? $\endgroup$ Dec 20, 2015 at 20:40
  • $\begingroup$ @CaptainCodeman The CAS I use don't have a good 2-d root finder. so I make an implicit plot for the real and imaginary part inside the unit disk, remember the point where they both vanishes and then apply 1-d root finder twice around those points to find the roots. It is not that accurate and slow... $\endgroup$ Dec 20, 2015 at 21:17
  • $\begingroup$ Thanks buddy, I really appreciate this. It's well over my level of mathematics knowledge, but maybe one day I'll be able to come back to this and understand it! $\endgroup$ Dec 22, 2015 at 20:31
1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ $g(x)$ has radius of convergence $1$. In fact, by Hadamard gap theorem, it has a natural boundary on the unit circle which you cannot analytic continue across it. $\endgroup$ Dec 22, 2015 at 1:50
  • $\begingroup$ Whoops, that is right. We can somewhat salvage this if we suppose that f(x)-1/(1-x) has a radius of convergence strictly larger than 1. $\endgroup$
    – mercio
    Dec 22, 2015 at 2:08
  • $\begingroup$ Actually that might be a consequence from the pn -> 1 hypothesis. $\endgroup$
    – mercio
    Dec 22, 2015 at 2:13
  • $\begingroup$ If $f(x)-1/(1-x)$ have a radius of convergence $R$ strictly larger than $1$, you argument does seem to work and I believe it do imply the uniqueness of the solution. However, I don't think you can deduce this condition on $R$ from the $p_n \to 1$ hypothesis. $\endgroup$ Dec 22, 2015 at 3:00
  • $\begingroup$ I have no idea what you guys are saying. What kind of book do I have to read to understand this? $\endgroup$ Dec 22, 2015 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.