Recurrences

Sat, Apr 22, 2017

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} $$