I'm studying discrete math in the university, and we are given questions and answers for some problems, and I dont understand most of them. So I need help understanding one of them... Appreciate the help!
Question:
Given the initial conditions and recurrence relation $a_{n}=a_{n-1}+6a_{n-2}-6$ , $a_{1}=1$ and $a_{2}=4$ . We have to find the equation that satisfies this recurrence relation.
Solution: So they claimed that our equation have to be in the form $a_{n}=c_{1}x_{1}^{n}+c_{2}x_{2}^{n}+c$ , (????) .
And then , apparently , $x_{1}$ and $x_{2}$ are the solutions for the equation $x^{2}=x+6$ (?????), where we get the solutions, $x_{1}=3$ and $x_{2}=2$
And $c$ is the solution for the equation $c=c-6c-6$ (????) which is $c=1$ and then we solve the the two equations $1=c_{1}3+c_{2}2$ and $6=c_{1}9+c_{2}4$ and we find $c_{1}$ and $c_{2}$ , and we have the equation as desired.
However I practically don't understand any step of this solution that was given, appreciate it if someone can explain these steps, and if someone can recommend me a book or something that I can learn the recurrence realtion much better because I am having trouble understanding the lectures... Thank you!
You start by finding the general solution, then the particular solution. So if your recurrence was homogenous, you would have: $a_{n} = a_{n - 1} + 6a_{n-2}$, which gives you the characteristic polynomial $\lambda^{2} - \lambda - 6 = 0$, with roots $\lambda = 3, -2$. So your general form equation is
$$a_{n} = c_{1}(3)^{n} + c_{2}(-2)^{n} + f(n)$$
That is, $f(n)$ is what we call a particular solution. Plugging it in will satisfy the recurrence. Since $a_{n} - a_{n-1} - 6a_{n-2} = 6$, we guess that $f(n) = c_{3}$, a constant and plug it into the recurrence. Since $f(n) = c_{3}$ is a particular solution, we will be able to solve for the constant
$$c_{3} - c_{3} - 6c_{3} = -6 \implies c_{3} = -1$$
So $a_{n} = c_{1}3^{n} + c_{2}(-2)^{n} + 1$.
Check:
$a_{1} = 1 = 3c_{1} - 2c_{2} + 1 \implies 3c_{1} - 2c_{2} = 0$
$a_{2} = 4 = 9c_{1} + 4c_{2} + 1 \implies 9c_{1} + 4c_{2} = 3$
Solving yields $15c_{1} = 3 \implies c_{1} = \frac{1}{5}$.
Then $c_{2} = \frac{3}{10}$.
So in short, the procedure is:
-Solve the recurrence as if it were homogenous to get the complementary solution.
-Guess at the particular solution based on the form of the extra term (which is $-6$ in this case).
-Solve for the particular solution by plugging it into the recurrence.
-Solve for the contents of the complementary solution.
Let me know if I can clarify.