# More Linear Recurrences

Let be defined by the recurrence relation , with . Show that the expression depends only on b and , but not on a.

In order to do this problem, we will first prove a few trivial properties of its system first.

#### is linear in

We show this inductively on the naturals. Suppose , then, we show

This concludes our proof that for some number , and is hence linear in .

Therefore , and without loss of generality, we can replace with any arbitrary number. We will pick for the sake of simplicity.

#### Guess and check

Let’s generate a few numbers for with

This naturally suggests that

(1)

#### Show that

We will prove this via induction on the naturals. Let , then from the table above, it is obvious that holds. We will now show that . Informally, we will expand the term within the first order recursive expansion of along with the equivalent construct . The body of the induction is as follows:

This concludes our proof that and the proof that does not depend on .

Woosh