# 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} AN &= (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}