On Fibonacci-style Sequences continued

In my previous post on Fibonacci-style sequences, I gave the formulae for the closed form

a_n = p \cdot r^n + q \cdot s^n

given the recurrence values a_0, a_1, b, c where

a_{n+2} = b \cdot a_{n} + c \cdot a_{n+1}

but I did not show that the formula is valid. I do that here.

In that previous post, the closed form was derived from its applications to n = 0, 1, 2.

We need to demonstrate that the formula continues to be valid for other values of n.

There, we showed that

b = - r s

c = r + s

We proceed by induction.

Consider two cases to be valid (as inductive hypotheses):

a_{n-1} = p \cdot r^{n-1} + q \cdot s^{n-1}

a_{n} = p \cdot r^{n} + q \cdot s^{n}

Now

a_{n+1} = b \cdot a_{n-1} + c \cdot a_{n}

{} = (- r s) (p \cdot r^{n-1} + q \cdot s^{n-1}) + (r + s) (p \cdot r^{n} + q \cdot s^{n})

{} = {} - r s p \cdot r^{n-1} - r s q \cdot s^{n-1}

{} + r p \cdot r^{n} + r q \cdot s^{n} + s p \cdot r^{n} + s q \cdot s^{n}

{} = {} - s p \cdot r^{n} - r q \cdot s^{n}

{} + p \cdot r^{n+1} + r q \cdot s^{n} + s p \cdot r^{n} + q \cdot s^{n+1}

{} = p \cdot r^{n+1} + q \cdot s^{n+1}

We have at least two base cases available. Hence by induction, the formula holds for all n.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: