  Close Menu Navigation

# 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