Finding the closed form for a sequence

Question

My teacher isn't great with explaining his work and the book we have doesn't cover anything like this. He wants us to find a closed form for the sequence defined by:

$P_{0} = 0$

$P_{1} = 1$

$\vdots$

$P_{n} = -2P_{n-1} + 15P_{n-2}$

I'm not asking for a straight up solution, I just have no idea where to start with it. The notes he gave us say:

We will consider a linear difference equation that gives the Fibonacci sequence.

$y(k) + A_1y(k -1) + A_2y(k -2) = \beta$

That's the general form for a difference equation in which each term is formed from the two preceding terms. We specialize this for our Fibonacci sequence by setting $A_1 = 1, $ >$ >A_2 = 1,$ and $ \beta = 0$. With some rearrangement, we get

$y(k) = y(k - 1) + y(k - 2)$

which looks more like the general form for the Fibonacci sequence.

To solve the difference equation, we try the solution $y(k) = Br^k$. Plugging that in, we obtain

$Br^{k-2} (r^2 - r - 1) = 0$

I have no idea where the $Br^k$ is coming from nor what it means, and he won't explain it in any sort of terms we can understand.

If someone could help me with the basic principle behind finding a closed form with the given information I would be eternally grateful.

---

EDIT: Using the information given (thank you guys so much) I came up with

$y(k) = \frac{1}{8}(3)^k - \frac{1}{8}(-5)^k$

If anyone has ran through let me know what you found, but I'm in no way asking you guys to do that. It's a lot of work to help some random college student.

Answer 1

Since you wrote "I have no idea where the $Br^k$ is coming from" and since Mhenni's solution, though perfectly correct, said to "just assume" such a solution, I think the following may help. There is a general theorem describing the solutions of linear recurrences of the form $X(n)=a_1X(n-1)+a_2X(n-2)+\dots+a_mX(n-m)$, where $m$ is fixed (in your examples it's $2$) and the $a_i$ are constants. Part of the theorem says that, if there are $m$ solutions of the special form $X(n)=r^n$ for $m$ different values of $r$, then every solution is obtainable as a linear combination of these $m$ special solutions. (There's also information in the theorem about what happens if there are not $m$ different solutions of that special form, but that additional information isn't relevant for your examples, so I'll postpone it to the last paragraph of this answer.)

In view of this (part of the) theorem, you can attack recurrence relations of this sort by first trying to find solutions off the special form $X(n)=r^n$. So plug this $X(n)$ into the recurrence, leaving $r$ unspecified for the time being. You get an equation that simplifies to $r^m=a_1r^{m-1}+a_2r^{m-2}+\dots+a_m$. This is a polynomial equation of degree $m$ for the unknown $r$. If it has $m$ different solutions (as it does in your examples), then you win. You have enough special solutions $X(n)=r^n$, one for each solution $r$, to invoke the general theorem. Any solution is a linear combination, with some constant coefficients, of these $m$ special solutions. You can determine the coefficients by using the initial conditions that were given with the recursion equation. This part of the job is quite easy, because it comes down to solving a system of linear equations for the unknown coefficients.

If $r^m=a_1r^{m-1}+a_2r^{m-2}+\dots+a_m$ has fewer than $m$ distinct roots, because some of the roots have multiplicity greater than $1$, then your recurrence has additional solutions of the form $X(n)=n^jr^n$, where $j$ ranges from $0$ up to but not including the multiplicity of the root $r$.

Answer 2

A related problem. Here is a start. Just assume your solution $P_n=r^n$ and plug in back in the eq. to find $r$

$$ P_{n} = -2P_{n-1} + 15P_{n-2} \implies r^n+2r^{n-1}-15r^{n-2}=0 $$

$$ \implies r^{n-2}(r^2+2r-15)=0 \implies r^2+2r-15=0 $$

Find the roots of the above polynomial $r_1, r_2$ and construct the general solution

$$ P(n)=c_1 r_1^n + c_2 r_2^n \longrightarrow (*) $$

To find $c_1$ and $c_2$, just use $P_0=0$ and $P_1=1$ in $(*)$ to get two equations in $c_1$ and $c_2$. Once you find $c_1$ and $c_2$ plug them back in $(*)$ and this will be the required solution.