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
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 .