# Finding the closed form for a sequence

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.

-
What course did this problem come from? –  Mhenni Benghorbal Apr 26 '13 at 20:27
CS 191, Computing Structures. –  Neal Apr 26 '13 at 20:29
So, you have studied about difference equations in this course? –  Mhenni Benghorbal Apr 26 '13 at 20:32
Not especially. The professor is scatterbrained and his lectures have little to no solid point. I've been using the book to teach myself most of the material. Currently in my sophomore year in college. –  Neal Apr 26 '13 at 20:33
That's what I expected, so, in my answer, I wanted to make sure you understand how find a solution of a linear difference equation with constant coefficient. It is a technique to find a SOLUTION just like a techniue to find a solution, for instance, a differential equation. –  Mhenni Benghorbal Apr 26 '13 at 20:42

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$.

-
If I had the 15 reputation necessary I would vote this up. I'm making real progress now, and finally understanding where it's all coming from. Much thanks. –  Neal Apr 26 '13 at 20:22

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.

-
Why am I setting $P_n = r^n$? I'm not sure why that assumption is allowed. Care to elaborate? –  Neal Apr 26 '13 at 20:07
This is one of the techniues how to find a solution for a linear difference equation with constant coefficient. There exist other techniues how to get a solutin. –  Mhenni Benghorbal Apr 26 '13 at 20:10