Error propagation through recurrence relation

Question

I want to see how the error propagates on a mapping that I have. I have proven that $$|f(x+\varepsilon)-f(x)|=\varepsilon(1+\varepsilon),$$ let $\varepsilon_n$ be the error after $n$ applications of the mapping, it holds $\varepsilon_{n+1}=\varepsilon_n(1+\varepsilon_n)$. It is easy to show $\varepsilon_n$ obeys $$\frac{\varepsilon_n}{\varepsilon_0}=\sum_{k=0}^{2^n} p_k(n) \varepsilon_0^k$$ with $p_k(n)$ polynomials. I have convinced myself that $p_k(n)$ is of degree $k$ and the coefficient of the highest order term is 1, which by the way is exactly what I need. However I cannot find how to prove it. I even have difficulties setting up an induction.

So, first of all, is this by any chance a known map? Can I find any results anywhere? Also any idea on how to prove this is more than welcome.

EDIT: Motivation

The motivation comes from trying to approximate the separatrices of a map. So I have a map $f:\mathbb{C}^2\to\mathbb{C}^2$ and let $w(s)$ be a separatrix parametrised by $s\in\mathbb{C}$ for which it holds $f(w(s))=w(s+1)$.

The problem is that I know $w(s)$ as an approximation by a formal series $w_N(s)=\sum_{i=1}^N w_i s^{-i}$ I also know that the error is of the order of $s^{-N}$.

I try to prove that $$\lim_{n\to\infty}f^n(w_N(s-n))=w(s)$$ this is possible because the error is not constant with $n$, for big $n$ the error is of the order $n^{-N}$ and if the error propagates as expected, then it goes to zero as $n$ goes to infinity.

Answer 1

Let $$\frac{\varepsilon_n}{\varepsilon_0}=\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k$$ where $f(k, n)$ is your $p_k(n)$.

Note that \begin{align} \sum_{k=0}^{\infty} f(k, n+1) \varepsilon_0^k=\frac{\varepsilon_{n+1}}{\varepsilon_0}& =\frac{\varepsilon_n(1+\varepsilon_n)}{\varepsilon_0} \\ &=\left(\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right)\left(1+\varepsilon_0\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right) \\ & =\left(\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right)+\varepsilon_0\left(\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right)^2 \\ &=\left(\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right)+\left(\sum_{k=0}^{\infty} \left(\sum_{j=0}^{k-1} f(j, n)f(k-1-j, n)\right)\varepsilon_0^k\right) \end{align}

Thus $$f(k, n+1)=f(k, n)+\left(\sum_{j=0}^{k-1} f(j, n)f(k-1-j, n)\right)$$

Note: This equation holds $\forall n,k \in \mathbb{Z}, n, k \geq 0$. In the following proof by strong induction, there is no restriction on $n$. Any equation with $n$ is assumed to hold for all non-negative integers $n$.

We now prove by strong induction on $k$ that $f(k, n)$ is a polynomial in $n$ of degree $k$ with leading coefficient $1$.

The above equation implies $f(0, n+1)=f(0, n)$ (the 2nd term with the sum is empty), so by induction $f(0, n)=1 \, \forall n \in \mathbb{Z}, n \geq 0$.

Suppose that the statement holds for $0 \leq k \leq l$. Then by the induction hypothesis, $f(i, n)f(l-i, n)$ is a polynomial in $n$ with degree $l$ and leading coefficient $1 \, \forall i$, so $f(l+1, n+1)-f(l+1, n)=\left(\sum\limits_{i=0}^{l} f(i, n)f(l-i, n)\right)$ is a polynomial in $n$ with degree $l$ and leading coefficient $(l+1)$. Thus there exists $a_0, a_1, \ldots , a_{l-1}$ such that $$f(l+1, n+1)-f(l+1, n)=(l+1)!\binom{n}{l}+\sum_{i=0}^{l-1}{a_i\binom{n}{i}}$$

Note: To see why this is true, note that both $f(l+1, n+1)-f(l+1, n)$ and $(l+1)!\binom{n}{l}$ are polynomials in $n$ with degree $l$ and leading coefficient $l+1$, so their difference is a polynomial in $n$ with degree $\leq (l-1)$. Any polynomial $P(n)$ can be written as a linear combination of binomial coefficients $\binom{n}{i}$, where $0 \leq i \leq deg(P(n))$, so in particular the above equation holds for some $a_i$.

Thus \begin{align} f(l+1, n)& =f(l+1, 0)+\sum_{j=0}^{n-1}{(f(l+1, j+1)-f(l+1, j))} \\ &=\sum_{j=0}^{n-1}{(f(l+1, j+1)-f(l+1, j))} \\ & =\sum_{j=0}^{n-1}{\left((l+1)!\binom{j}{l}+\sum_{i=0}^{l-1}{a_i\binom{j}{i}}\right)} \\ & =(l+1)!\binom{n}{l+1}+\sum_{i=0}^{l-1}{a_i\binom{n}{i+1}} \end{align}

Note:$f(l+1, 0)=0$ since $l+1 \geq 1$ and $1=\frac{\varepsilon_0}{\varepsilon_0}=\sum_{k=0}^{\infty} f(k, 0) \varepsilon_0^k$.

This is indeed a polynomial in $n$ of degree $l+1$ and leading coefficient $1$.

We are thus done by strong induction.

Answer 2

Sorry, but $\epsilon_{n + 1} = \epsilon_n (1 + \epsilon_n)$ diverges (if $\epsilon_n > 0$ then $1 + \epsilon_n > 1$, and $\epsilon_{n + 1} > \epsilon_n$).