# Closed form solution of recurrence relation

I am asked to solve following problem Find a closed-form solution to the following recurrence: \begin{align} x_0 &= 4,\\ x_1 &= 23,\\ x_n &= 11x_{n−1} − 30x_{n−2} \mbox{ for } n \geq 2. \end{align}

When I have searched what does mean closed-form solution, wikipedia gives me answer that it is expressed by the following statement

An expression is said to be a closed-form expression if it can be expressed analytically in terms of a bounded number of certain "well-known" functions.

-
In what context is this question being asked? An answer that works for you depends on what you know and what is expected of you. For instance, there is a clear answer based on Linear Algebra and diagonalizing matrices. Does this make any sense to you? –  lhf Aug 19 '11 at 13:30

What you are being asked for is an equation that has $x_n$ on the left side and a formula in $n$ on the right side containing just familiar functions like polynomials and exponentials and only finitely many of them. Whoever asked you to solve the problem probably also provided a method for solving such problems, but here goes:

First, let's write your problem in a better format: $x_0=4$, $x_1=23$, $x_n=11x_{n-1}-30x_{n-2}$.

Now, suppose there is a solution of the form $x_n=c^n$ for some $c$. (Why do we make such a supposition? Because we've been here before, and we know it will work.) Then the equation says $c^n=11c^{n-1}-30c^{n-2}$, which simplifies to $c^2-11c+30=0$, which undoubtedly you are able to solve. You'll get two values of $c$ that work, let's call them $c_1$ and $c_2$, and then anything of the form $Ac_1^n+Bc_2^n$ will work also, for any numbers $A$ and $B$. If you're clever in choosing $A$ and $B$, you'll get $x_0=4$ and $x_1=23$.

-
really i did not know this before thanks @Gerry Myerson i have gained one more expierence after this question thanks ones again –  dato datuashvili Aug 19 '11 at 13:37
@useer3196: there is a writeup at en.wikipedia.org/wiki/Recurrence_relation that may help get you started. What you have is a "Linear homogeneous recurrence relations with constant coefficients" which gets its own section –  Ross Millikan Aug 19 '11 at 14:06
thanks @ Ross Millikan –  dato datuashvili Aug 19 '11 at 14:19
There no need for irrational magic. Instead of pulling rabbits out of a hat ("make such a supposition") one can use rational deduction. Namely, the solution follows simply by factoring a polynomial - see my answer –  Bill Dubuque Aug 19 '11 at 16:13
No one pulled a rabbit from a hat. We merely make use of what we have seen someone else do. Somebody had to hit upon the method, whether by irrational magic or rational deduction, but then the rest of us can make use of what that pioneer has discovered for us. –  Gerry Myerson Aug 19 '11 at 23:24

HINT $\$ Let $\rm\:S\:$ be the shift-operator $\rm\:S\ f(n) = f(n+1)\:.\:$ Then your recurrence factors as follows

$\rm\qquad\qquad 0\ =\ f(n+2) - 11\ f(n+1) + 30\ f(n)$

$\rm\qquad\qquad\ \ \ =\ (S^2 - 11\ S + 30)\ f(n)$

$\rm\qquad\qquad \ \ \ =\ (S-5)\ (S-6)\ f(n)$

Now $\rm\:(S-6)\ f(n) = 0\ \iff\ f(n+1) = 6\ f(n)\ \iff\ f(n) = c\:6^n\$ for $\rm\:c\:$ constant, i.e. $\rm\:S\:c = c\:.$

and $\rm\:\ \ (S-5)\ f(n) = 0\ \iff\ f(n+1) = 5\ f(n)\ \iff\ f(n) = d\:5^n\$ for $\rm\:d\:$ constant.

Because $\rm\:S-5\:$ and $\rm\:S-6\:$ commute, we infer that $\rm\: c\ 6^n + d\ 5^n\:$ is a solution for all constants $\rm\:c,d\:.\:$ Now plug in the known initial conditions $\rm\:f(0) = x_0,\ f(1) = x_1\:$ to solve for the unknowns $\rm\:c,d\:.$

-
"Shoulders of Giants" is a great location! –  lhf Aug 19 '11 at 15:53

Use generating functions. Define $X(z) = \sum_{n \ge 0} x_n z^n$, rewrite your recurrence without subtractions in indices: $$x_{n + 2} = 11 x_{n + 1} - 30 x_n$$ Multiply the recurrence by $z^n$, sum over all valid values of $n$ (i.e., $n \ge 0$), and recognize the resulting sums: $$\frac{X(z) - x_0 - x_1 z}{z^2} = 11 \frac{X(z) - x_0}{z} - 30 X(z)$$ Solve for $X(z)$, write as partial fractions: $$X(z) = \frac{3}{1 - 6 z} + \frac{1}{1 - 5 z}$$ Two geometric series, so: $$x_n = 3 \cdot 6^n + 5^n$$

-
thanks very much +1 –  dato datuashvili May 16 '14 at 18:12