Recurrences

Sat, Apr 22, 2017 02:00 CEST

Tags: Recurrences

Theorem

Let \(a \in \mathbb{N} \), \(t < a \in \mathbb{N} \), and \(b \in \mathbb{R}\). Defining \(A_t\)to be some real number and

$$ A_N = (1 - \frac{a}{N}) A_{N-1} + b, N > t \in \mathbb{N}, $$

then

$$ A_N = \frac{b}{1+a} (N+1), N \ge a \in \mathbb{N}. $$

Proof

Since \(t < a \), \(A_N\) with \(N \ge a\) does not depend on \(A_t\) because

$$ A_a = (1 - \frac{a}{a}) A_{a-1} + b = b. $$

Now we can check that the theorem holds for \(N = a\):

$$ A_a = \frac{b}{1+a} (a+1) = b. $$

And by induction for \(N > a\),

$$ \begin{aligned} A_N &= (1 - \frac{a}{N}) A_{N-1} + b \\ &= (1 - \frac{a}{N}) \frac{b}{1+a} N + b \\ &= \frac{b}{1+a} N - \frac{ab}{1+a} + b \\ &= \frac{b}{1+a} N - \frac{ab}{1+a} + \frac{b+ab}{1+a} \\ &= \frac{b}{1+a} N + \frac{b}{1+a} \\ &= \frac{b}{1+a} (N+1). \end{aligned} $$