Closed form solution of recurrence relation

Solution 1:

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

Solution 2:

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

Solution 3:

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

Solution 4:

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.