# Recursive equations critical boundary

I have an interesting problem and i don't have any idea about how to solve it :-)

I'm given a system of $K$ equations (with $N \gt K$ , and $0 \lt f \lt 1$)

$$f(1-f)^{K-1} - (1-f)^{N-K} \alpha_K = 0$$ $$f(1-f)^{K-2} - (1-f)^{N-K} \alpha_{K-1} (1 - f - \alpha_K) = 0$$ $$\ldots$$ $$f - (1-f)^{N-K} \alpha_1 \Pi_{i=2}^{K}(1-f- \alpha_i) = 0$$

The end goal is to find the set of values of $f$ and $N$ for which the system has solutions for which $0 \lt 1 - f - \alpha_i \lt 1$ for all the range of $N \gt K \gt 0$, which (i think) is equivalent to asking that $\Pi_{i=j}^{K}(1-f- \alpha_i) \lt 1$. I refer to this quantity as the remainder flux, because it can be interpreted as the net coefficient of attenuation after each node consumes a fixed ratio $f$ and a variable ratio $\alpha_i$

I've found a simple recursive solution for the $\alpha$ as

$$\alpha_K = f ( 1-f)^{2K - N-1}$$ $$\ldots$$ $$\alpha_{j-1} = \frac{f (1-f)^{K - N + j - 1} }{ \Pi_{i=j}^{K}(1-f- \alpha_i) }$$

Doing some numerical experiments i've found that for $N=4000$ , $f=10^{-3}$, the system for $K=18$ is the highest for which there are solutions that satisfy the condition, but for $K=19$ the remainder flux becomes above one for $j=1$. On the other hand, for $f=10^{-4}$, the system has solutions for all $K \lt 4000$

I've been looking into how to figure how to find what values of $f$ and $N$ will produce "stable" solutions. Are there any suggestions that can help me?

-
ok, i think i found a solution, i'll post it later after i've worked it all out – lurscher Feb 25 '13 at 17:02

## 2 Answers

Continuing your solution, if $(1-f)^N = \frac{ f }{ 1 + f - (1 - f)^2 }$, $(1-f)^N =\frac{ f }{ 1 + f - 1 +2f- f^2 } = \frac{ f }{ 3f- f^2 } = \frac1{ 3- f }$.

If $f$ is small, $(1-f)^N = \frac1{3}$ or $1-f = \frac1{3^{1/N}}$ or $f = 1-\frac1{3^{1/N}} = 1-3^{-1/N} = 1-e^{-\ln (3/N)} \approx 1-(1-(\ln (3/N)) = \ln (3/N)$.

This does not agree with your final equation.

If I use the previous equation, and assume that $f$ is small, it becomes $(1-f)^N(1-(1-f)^N) \approx 2f^2$.

If $f$ is small compared to $1/N$, which may not be true by your computation, this becomes $(1-Nf)(Nf) \approx 2f^2$ or $1-Nf \approx 2f/N$ or $f \approx 1/(N+2/N) \approx 1/N$. For $N=4000$, this gets $f \approx 2.5\times 10^{-4}$, which is not too far from your computation.

As a guess, I would say that $f$ has an expansion of the form $a/N + b/N^2$ for $a$ close to $1$ and some $b$.

-
i've updated the answer incorporating your observations, thanks! – lurscher Mar 15 '13 at 18:15

a recursive solution is given in the following form:

$$\alpha_k^{-} = f (1- f)^{2k - N - 1}$$ $$\alpha_{k-1}^{-} = \frac{ f (1- f)^{2k - N - 2} }{ 1 - f - \alpha_k^{-} }$$ $$\ldots$$ $$\alpha_{1}^{-} = \frac{ f (1- f)^{k - N} }{ \displaystyle \Pi_{i = 2}^{k} ( 1 - f - \alpha_i^{-}) }$$

For a given configuration of $N$ nodes, the critical configuration happens when the available remaining flux is zero at the endpoint.

We translate the above insight as the following condition (1):

$$1 - f - \alpha_1^{-} = 0$$

This translates to

$$1 = \frac{ f (1- f)^{k - N - 1} }{ \displaystyle \Pi_{i = 2}^{k} ( 1 - f - \alpha_i^{-}) }$$

$$1 - f - \alpha_2^{-} = \frac{ f (1- f)^{k - N - 1} }{ \displaystyle \Pi_{i = 3}^{k} ( 1 - f - \alpha_i^{-}) }$$

$$1 - f - \alpha_2^{-} = \frac{ \alpha_2^{-} }{ ( 1 - f)^2 }$$

$$\alpha_2^{-} = \frac{ (1-f)^3 }{ 1 + ( 1 - f)^2 }$$

By induction we can prove that

$$\alpha_k^{-} = \frac{ (1-f)^{2k-1} }{ \displaystyle \sum_{i=0}^{k-1} (1-f)^{2i} }$$

which is equivalent to

$$\alpha_k^{-} = \frac{ (1-f)^{2k-1} \lbrack 1 - (1-f)^2 \rbrack }{ 1- (1-f)^{2k} }$$

By equating this to condition (1), and taking $2k = N$, we have

$$f = \frac{ (1-f)^N \lbrack 1 - (1-f)^2 \rbrack }{ 1- (1-f)^{N} }$$

After a bit of manipulation this can be expressed as

$$(1-f)^N = \frac{ f }{ 1 + f - (1 - f)^2 } = \frac{ 1 }{ 3 - f }$$

$$(3-f)(1-f)^N= 1$$

$$N = - \frac{ \log{(3-f)} }{ \log{(1-f)} }$$

Fixing $N$, this can be solved numerically for $f$.

For $N=4000$, we find that $f=2.746 \times 10^{-4}$ is the maximum value for which consistent solutions exists.

-