Second order recurrence relations

Hello!

New here.

I'm stuck on a proof from a textbook called Discrete Mathematics by Epp.

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

This means that $\displaystyle t^{n} = At^{n-1} + Bt^{n-2}$.

Using n = 2, you end up with the quadratic $\displaystyle t^{2} - At - B = 0$, 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 [$\displaystyle a_{n} = Aa_{n-1} + Ba_{n-2}$]?"

To answer this, Epp multiplies the quadratic by $\displaystyle t^{n-2}$.

Here’s my issue: I don’t understand the point of the first part. Why not just start with the quadratic and multiply by $\displaystyle t^{n-2}$? This shows that the sequence $\displaystyle 1, t^{1}, t^{2}, t^{3},$…,t^{n}… satisfies $\displaystyle a_{n} = Aa_{n-1} + Ba_{n-2}$ (since $\displaystyle t^{n} = At^{n-1} + Bt^{n-2}$ is derived from the quadratic by multiplying by $\displaystyle t^{n-2}$) when t is equal to the roots of the quadratic. Why suppose that there is a sequence 1, t, t^2,... 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.

Re: Second order recurrence relations

Quote:

Originally Posted by

**hachataltoolimhakova** Hello!

New here.

I'm stuck on a proof from a textbook called Discrete Mathematics by Epp.

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

This means that $\displaystyle t^{n} = At^{n-1} + Bt^{n-2}$.

Using n = 2, you end up with the quadratic $\displaystyle t^{2} – At - B = 0$, 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 [$\displaystyle a_{n} = Aa_{n-1} + Ba_{n-2}$]?"

To answer this, Epp multiplies the quadratic by $\displaystyle t^{n-2}$.

Here’s my issue: I don’t understand the point of the first part. Why not just start with the quadratic and multiply by $\displaystyle t^{n-2}$? This shows that the sequence $\displaystyle 1, t^{1}, t^{2}, t^{3},$…,t^{n}… satisfies $\displaystyle a_{n} = Aa_{n-1} + Ba_{n-2}$ (since $\displaystyle t^{n} = At^{n-1} + Bt^{n-2}$ is derived from the quadratic by multiplying by $\displaystyle t^{n-2}$) when t is equal to the roots of the quadratic. Why suppose that there is a sequence 1, t, t^2,... 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.

The point is it demonstrates where the characteristic equation comes from. Seeing this you should be able to use the same technique to find the characteristic equation in other situations.

Also many people do not like it if a book or teacher pulls things out of the air and then demonstrates that they solve the problem at hand.

CB

Re: Second order recurrence relations

Thanks for the response CB.

Couldn't you make the same argument about the first part? It says "suppose" that a sequence 1, t, t^{2},... satisfies the recurrence relation. But why? Why should I "suppose" such a sequence satisfies the recurrence relation? This is only demonstrated, from my understanding, after the quadratic has been multiplied by t^{n-2}. I do not know why I should make the supposition that the sequence satisfies the recurrence relation, where did it come from? I can at least see, a posteriori, that multiplying the quadratic by t^{n-2} yield the recurrence relation; and you can therefore, having established this, see that the values of t are the roots of the quadratic. It just seems that to arrive at the conclusion would be more likely by starting with the quadratic and observing that multiplying it by t^{n-2} yields a recurrence relation of the form at^n-1 = bt^n-2 = t^n.

Thanks again CB.

Re: Second order recurrence relations

Quote:

Originally Posted by

**hachataltoolimhakova** Thanks for the response CB.

Couldn't you make the same argument about the first part? It says "suppose" that a sequence 1, t, t^{2},... satisfies the recurrence relation. But why? Why should I "suppose" such a sequence satisfies the recurrence relation?

One reason for supposing this is by observation of numerical and other experiments, and another is by analogy from the equivalent differential equations.

The secret that you may never discover in a maths course is that maths uses a lot of experiments (and analogy) to give clues about what direction to pursue in discovering results.

Conjectures are often the left over experimental/analogical results that no one has yet been able to prove or disprove.

CB

Re: Second order recurrence relations