Prove $\epsilon_n\le c^{f_n}$ where $f_n$ is the Fibonacci sequence by induction

Question

Let $f\in C^2(a, b)$ assume that $|f'(x)|\ge \delta > 0$ for all $x \in [a, b], f(p) = 0$ and that the secant method defines a sequence $\{p_n\}$ converging to $p$.

I showed that $|e_{n+1}| = |\frac{f''(\alpha_1)}{f'(\alpha_2)}e_ne_{n-1}|$ for every $n\ge 1$ and for some $\alpha_1,\alpha_2 \in [a, b]$.

I showed that $|e_{n+1}| \le M|e_n||e_{n-1}|$ for some constant $M$.

I also showed that $\epsilon_{n+1}\le\epsilon_n\epsilon_{n-1}$ given $\epsilon_n:=M|e_n|$.

How can I show that if $p_0$ is close enough to $p$, there exists $0\le c < 1$ such that for every $n\ge 2$, then $\epsilon_n\le c^{f_n}$ where $f_n$ is the Fibonacci sequence by induction?

Thank you all.

Answer 1

Any sequence solving the recursion $$ g_{n+1}=g_n+g_{n-1} $$ can be expressed via the Fibonacci-sequence with $f_0=0$, $f_1=1$ (and thus $f_{-1}=1$) as $$ g_n=g_1f_n+g_0f_{n-1} $$ Now set $g_0=\ln(ϵ_0)$, $g_1=\ln(ϵ_1)$ and prove by induction that $ϵ_k\le e^{g_k}$. This is true for $k=0,1$ and if true up to $k\le n$, then also $$ ϵ_{n+1}\le ϵ_{n}ϵ_{n-1}\le e^{g_n+g_{n-1}}=e^{g_{n+1}} $$ Now use something like $f_{n-1}\le f_n$ for $n>0$ to get to the claim.

Answer 2

I will show that if $\epsilon_n \le c^{f_n} $ and $\epsilon_{n-1} \le c^{f_{n-1}} $ then $|\epsilon_{n+k}| \le c^{f_{n+k}} $ for $k \ge 1$.

Proof.

$\begin{array}\\ |\epsilon_{n+1}| &\le |\epsilon_n||\epsilon_{n-1}|\\ &\le c^{f_n}c^{f_{n-1}}\\ &= c^{f_n+f_{n-1}}\\ &= c^{f_{n+1}}\\ \end{array} $

Then proceed by induction.

We can choose $c =\max(\epsilon_{n-1}^{1/f_{n-1}}, \epsilon_{n}^{1/f_{n}}) $.