Second Order Homogeneous Recurrence Relation

[nobahar]

Hello!

I was reading the proof (I think it constitutes a proof) for second order homogeneous recursive relations from the book Discrete Mathematics with Applications by S. Epp, and it seems, to me at least, to be excessive; which suggests that I don’t understand the proof.

It goes something like the following (the proof is here: http://books.google.co.uk/books?id=...er homogeneous recurrence relations&f=false):

Firstly, there is the recurrence relation [itex]a_{n} = Aa_{n-1} + Ba_{n-2}[/itex], then the book states that “uppose that for some number t… the sequence 1, t^{1}, t^{2}, t^{3},…,t^{n},….
satisfies [[itex]a_{n} = Aa_{n-1} + Ba_{n-2}[/itex]].”

This means that [itex]t^{n} = At^{n-1} + Bt^{n-2}[/itex].

Using n = 2, you end up with the quadratic [itex]t^{2} – At – B = 0[/itex], from which you can derive the values for t (the roots of the quadratic).

The book then states: “Now work backward. Suppose t is any number that satisfies [the quadratic]. Does the sequence 1, t^{1}, t^{2}, t^{3},…,t^{n},…. satisfy [[itex]a_{n} = Aa_{n-1} + Ba_{n-2}[/itex]]?”

To answer this, Epp multiplies the quadratic by [itex]t^{n-2}[/itex].

Here’s my issue: I don’t understand the point of the first part. Why not just start with the quadratic and multiply by [itex]t^{n-2}[/itex]? This shows that the sequence [itex]1, t^{1}, t^{2}, t^{3},…,t^{n},….[/itex] satisfies [itex]a_{n} = Aa_{n-1} + Ba_{n-2}[/itex] (since [itex]t^{n} = At^{n-1} + Bt^{n-2}[/itex] is derived from the quadratic by multiplying by [itex]t^{n-2}[/itex]) when t is equal to the roots of the quadratic. Why suppose that there is a sequence 1, t, t²,… that satisfies the recurrence relation then work towards the quadratic formula? I don’t see what it demonstrates? Why not just start with the quadratic and show such a relation exists, and work from there?

Any help appreciated.

 

[nate808]

Thank you for bringing up your confusion with the proof for second order homogeneous recursive relations. I understand the importance of fully understanding mathematical proofs and I am happy to provide some clarification for you.

The reason for starting with the recurrence relation a_n = Aa_{n-1} + Ba_{n-2} and then introducing the sequence 1, t, t^2, ... is to show that the recurrence relation can be satisfied by a sequence with a specific form. In other words, by choosing t to be the roots of the quadratic t^2 - At - B = 0, we can construct a sequence that satisfies the recurrence relation.

By working backwards and multiplying the quadratic by t^{n-2}, we are essentially showing that the sequence 1, t, t^2, ... satisfies the recurrence relation for any value of t that satisfies the quadratic equation. This is important because it shows that there is not just one sequence that satisfies the recurrence relation, but rather an infinite number of sequences that can be constructed using the roots of the quadratic.

Starting with the quadratic equation and showing that it satisfies the recurrence relation may seem simpler, but it does not fully demonstrate the concept of finding a sequence that satisfies the recurrence relation. By introducing the sequence first, we are able to show the relationship between the recurrence relation and the quadratic equation in a more concrete manner.

I hope this explanation helps to clarify the proof for you. If you have any further questions, please do not hesitate to ask. As scientists, it is important for us to fully understand and question mathematical proofs in order to advance our knowledge and understanding. Keep up the good work in your studies!