Recurrence Relations – Closed Form Solution

recurrence-relations

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.

Best Answer

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

Related Question