Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

So in this case we must find functions bounds or what? Please help me.

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
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 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\:.$

share|cite|improve this answer
"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 $$

share|cite|improve this answer
thanks very much +1 – dato datuashvili May 16 '14 at 18:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.