Solving x = a x + b

Problem: Solving x = ax +b for x.

Solution:

Choose x_0 arbitrarily, we generate the sequence \{x_i\} recursively from x_i = a x_{i-1} + b, i=1, 2, ...:

x_1= a x_0 + b,

x_2 = a x_1 +b =a(a x_0+b)+b =a^2 x_0 +ab + b,

x_3 = a x_2 + b = a (a^2 x_0 + ab +b) +b = a^3 x_0 +a^2b +ab +b,

\ddots

x_n = a x_{n-1} +b = a^n x_0 + b \sum\limits_{i=0}^{n-1} a^i=a^n x_0 + b\cdot\frac{1-a^{n}}{1-a}.

It follows that for |a| <1,

x = \lim\limits_{n \rightarrow \infty} x_n = \lim\limits_{n\rightarrow \infty}a^n x_0+\frac{b(1-a^n)}{1-a}= \lim\limits_{n\rightarrow \infty}a^n x_0+ \lim\limits_{n \rightarrow \infty}\frac{b(1-a^n)}{1-a}\overset{(\star)}{=}0\cdot x_0 + \frac{b(1-0)}{1-a}.

i.e.,

x = \frac{b}{1-a}.

Fig. 1 shows a CAS -aided solution using Omega CAS Explorer:

Fig. 1

For |a|> 1, we rewrite x=ax +b as

x = \frac{1}{a}x - \frac{b}{a} \overset{A=\frac{1}{a}, B=-\frac{b}{a}}{=} Ax +B.

Since |a| >1 \implies \frac{1}{|a|} = |A| <1\implies \lim\limits_{n\rightarrow \infty}A^n = 0,

x =\lim\limits_{n \rightarrow \infty}A^n x_0 + B\cdot \frac{1-A^n}{1-A}\frac{}{} = \frac{B}{1-A} = \frac{-\frac{b}{a}}{1-\frac{1}{a}} = \frac{-b}{a-1} = \frac{b}{1-a}.


We have used fact that

|a| < 1 \implies \lim\limits_{n \rightarrow \infty} a^n = 0.\quad\quad\quad(\star)

A proof is as follows:

Since

|a^n| = |\underbrace{a\cdot a\cdot a ... a}_{n\;a's}| =\overbrace{|a||a|...|a|}^{n\;|a|'s} = |a|^n,

if a=0 then a^n = 0\cdot 0 ... 0 = 0. It means

(\forall \epsilon >0,  \forall n \in N^+, |a^n-0|<\epsilon)\implies \lim\limits_{n \rightarrow \infty} a^n = 0.

Otherwise (a \ne 0),

\forall \epsilon >0, |a^n-0| =|a|^n < \epsilon \implies n \log(|a|)<\log(\epsilon).

For |a|<1,

n\log(|a|)<\log(\epsilon) \overset{\log(|a|) < 0}{\implies} n > \frac{\log(\epsilon)}{\log(|a|)}.

And so,

(\forall \epsilon > 0, \exists n^* =  \lceil\frac{\log(\epsilon)}{\log(|a|)}\rceil \ni  n > n^*, |a^n-0| < \epsilon) \implies \lim\limits_{n \rightarrow \infty}a^n = 0.


Exercise-1 Prove by mathematical induction:

(x_{k} = a x_{k-1} + b, k=1,2,...,n ) \implies x_n = a^n x_0 + b\sum\limits_{i=0}^{n-1}a^i.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s