# Show convergence of recursive function given different initial values

Well, I never had to show something like this which is why I'm having quite a hard time to get this one done. I basically know what I have to do but I am not capable of solving it properly.

Given for example: $U = 0.25, F = 0.01, \Delta t = 0.1$

\begin{align*} u_k &= U + \underbrace{u_{k-1}(1-U)}_\text{A} \,\underbrace{e^{-\Delta t /F}}_\text{B} \end{align*}

Well, since $U$ is constant, the only interesting things are $A$ and $B$.

I know that $A$ itself converges to $0$. The problem is I don't know how I can show that analytically. $B$ also would regulate the whole term that is added to $U$ so in the end it will determine the value where $u_k$ will converge to.

As far as I understood it $u_0 = U$.

Could someone explain to me a technique that would allow me to solve such an equation?

So basically, what is $\lim_{k\rightarrow\infty} u_k$.

## General Formula for an Arithmetico-Geometric Sequence

Since $U$, $\Delta t$ and $F$ are constant, your recursion reduces to an arithmetico-geometric sequence: $$u_k=a\cdot u_{k-1}+b$$ If we let $r=\dfrac{b}{1-a}$, we get: $$u_n=a^n(u_o-r)+r$$

## Specific Example

In your particular case, we have: $a=\dfrac{0.75}{e^{10}}$ and $b=u_0=0.25$, such that: $$u_n=\left(\dfrac{0.75}{e^{10}}\right)^n\left(0.25-\dfrac{0.25}{1-\frac{0.75}{e^{10}}}\right)+\dfrac{0.25}{1-\frac{0.75}{e^{10}}}$$ Since $0<\dfrac{0.75}{e^{10}}<1$, we have: $$\lim_{n\to\infty}u_n=0+\dfrac{0.25}{1-\frac{0.75}{e^{10}}}\simeq 0.250009$$

## Proof of the General Formula

Consider the sequence: $$u_k=a\cdot u_{k-1}+b$$ and let $w_{k-1}=u_k-u_{k-1}$, such that: $$w_k=u_{k+1}-u_k=(a\cdot u_k+b)-(a\cdot u_{k-1}+b)=a(u_k-u_{k-1})=a\cdot w_{k-1}$$ Thus $w_n$ is a geometric sequence of ratio $a$ and first term $w_0=u_1-u_0=(a-1)u_0+b$. From the definition of $w_k$ as the difference of $u_k$ and $u_{k-1}$, we have that: $$\sum_{k=0}^{k=n}w_k=u_n-u_0$$ And from the definition of $w_k$ as a geometric sequence: $$\sum_{k=0}^{k=n}w_k=w_0\dfrac{a^n-1}{a-1}=\dfrac{(a-1)u_0+b}{a-1}(a^n-1)$$ Let $r=\dfrac{b}{1-a}$, and equate the two sums above: $$u_n-u_0=(u_0-r)(a^n-1)$$ And finally we recover the general formula: $$u_n=a^n(u_0-r)+r$$

• Okay that means I can do that with anything as long I can rewrite it to a form like $u_k = a \cdot u_{k-1} + 1$, right? Would you call something like this something like "linear" recursive equation? And is a more general approach too far-reaching? I mean like if there is an approach I could use to solve even more complex recursive equations? I don't expect you to answer this my question is answered with what you provided already but I wouldn't mind some more explanation. :) Thank you in any case! – displayname May 4 '15 at 20:41
• As long as you can rewrite it as $u_k=a\cdot u_{k-1}+b$, with $a$ and $b$ constant, yes. This is not the most general approach, but when you're given a recursion and need to find if it converges, it's always a good thing to check if it is not by any chance a "nice" recursion (arithmetic, geometric or arithmetico-geometric sequences). Because in these cases, you can easily obtain a closed-form formula, and the limit follows naturally. – Demosthene May 4 '15 at 20:46
• Okay, thank you. I guess you just "need an eye" for things like that on the long run. If things like that come up more often I think I'll have to learn a little more about such equations. – displayname May 4 '15 at 20:53