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.

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

• 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
• 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
• Yes, just do A+B=4, 5A+6B=23, from this we deduce $a=1,b=3$, so the generating function is simply $x_n=5^n+3*6^n$ – Kai Jun 13 at 0:16

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

Please note this is my first time answering, so help me improve by keeping comments constructive

This is the characteristic polynomial method for finding a closed form expression of a recurrence relation, similar and dovetailing other answers:

given: $f(0)=v_1$, $f(1)=v_2$, ..., $f(d-1)=v_{d-1}$ and $a_df(n) + a_d−1f(n − 1) + · · · + a_0f(n-d) = 0$ for all $n ≥ 0$

Note, you likely need to rewrite the recurrence relation, for example, as your recurrence relation presents $x_n = 11x_{n-1} - 30x_{n-2}$ becomes $x_n-11x_{n-1}+30x_{n-2}=0$

The characteristic polynomial of this recurrence relation is of the form:

$q(x) = a_dx^d + a_{d−1}x^{d−1} + · · · + a_1x + a_0$

Now it's easy to write a characteristic polynomial using the coefficents $a_d$,$a_{d-1}$, ..., $a_0$:

$q(r)=r^2-11r+30$

Since $q(r) = 0$, the geometric progression $f(n) = r^n$ satisfies the implicit recurrence.

IF the roots of the characteristic equation are distinct, $f(n) = λ_1r_1^n + λ_2r_2^2 + · · · + λ_dr_d^n$, where $λ_1, . . . , λ_d$ are arbitrary complex numbers.

In this case, we have:

$q(r)=r^2-11r+30$

$q(r)=(r-5)(r-6)$

$r_1=5$ and $r_2=6$

So the general solution is:

$x_n=λ_15^n + λ_26^n$

Use the initial values to get two equations with two unknowns:

$f(0)=λ_15^0 + λ_26^0$

$4=λ_1 + λ_2$

$f(1)=λ_15^1 + λ_26^1$

$23=5λ_1 + 6λ_2$

Solving this, we have $λ_1 = 1$ and $λ_2=3$, so the solution is

$x_n=5^n + 3*6^n$

IF the roots are NOT distinct, we need to think a bit further, but we'll leave that for another time.

Starting from the formula: $$x_n = 5^n + 3 \cdot 6^n$$

Another way to see that same formula, is:

$$x_n = 3^{1/2} \cdot 30^{n/2} \cdot (3^{1/2} \cdot (6/5)^{n/2}+3^{-1/2}(6/5)^{-n/2})$$

Let: $$t_n = \frac {ln(3) + ln(30) \cdot n} {2}$$ Let: $$v_n = \frac {ln(3) + ln(6/5) \cdot n} {2}$$

Then: $$x_n = 2 \cdot exp(t_n) \cdot cosh(v_n)$$

Note: The numbers 6 and 5 of teh formula, is the two roots of: $$z^2 -11z +30 = 0$$