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.