Reduction of Order For Recursions

This is not meant as a full introduction to recursion relations but it should suffice for just about any level of the student.

Most of us remember recursion relations from secondary school. We start with a number, say, 1. Then we add 3. That gives us 4. Now we that number and add 3 again and get 7. And so on. This process creates a series of numbers $\{ 1, 4, 7, 10, \dots \}$. Once we get beyond that stage we start talking about how to represent these. Well, let’s call the starting number $a_0$. Then the next number in the series would be $a_1$, then $a_2$, …, on to $a_n$ where n is the nth number in the series. We may now express our recursion as a rule: $a_{n +1} = a_n + 3$, where $a_0 = 1$.

We may go much further. We can talk about things like the Fibonacci series: $F_{n + 2} = F_{n + 1} + F_{n}$, where $F_1 = F_2 = 1$. This is the famous series $\{ 1, 1, 2, 3, 5, 8, 13, \dots \}$. But what if we want a formula to find out what $F_n$ is for the nth number in the series? This is the purpose of this paper. As a nice side effect, it turns out that the method presented here can be applied to Differential Equations as well, which puts it squarely in the focus of Physics and Engineering. I will be spending most of the time talking about recursions, which are simpler to apply, but I will make sure to include a few examples of Differential Equations to show how that is done as well.

What I am calling “reduction of order” is a method similar in concept to, but not quite the same as, the method used in Differential Equations. The idea is to take an mth order homogeneous recursion and reduce it to an m-1th order inhomogeneous recursion which, in theory, should be easier to solve. In Differential Equations, it is typical to be given a solution to the original equation and derive another solution based on that. This method does not use that step.

What follows is a series of examples that will make the method clear.

First Order Homogeneous Recursions

This example is going to be a bit long but I need to point out a few concepts on the way.

Solve

$(1.1) ~~~~~ n a_n + 3 a_{n+1} = \dfrac{1}{n+1}$

The recursion is linear so we may put $a_n = h_n + p_n$. We start by solving the homogeneous recursion

$n h_n + 3 h_{n+1} = 0$

Now we reduce the order. We want to write a new, inhomogeneous, recursion of one order lower that has the same solution, with a leading coefficient of 1. In this case, let $h_n = g(n)$. Then

$n g(n) + 3 g(n +1) = 0$

$g(n + 1) = – \dfrac{n}{3} g(n)$

So

$g(n + 1) = – \dfrac{n}{3} g(n) = (-1)^2 \dfrac{n}{3} \dfrac{n -1}{3} g(n – 1) = \dots = (-1)^n \dfrac{n}{3} \dfrac{n- 1}{3} \dots \dfrac{2}{3} \dfrac{1}{3} g(1) \equiv (-1)^n A \left ( \dfrac{n}{3} \right )!$

where f(n)! is a “functional factorial” defined as

$\displaystyle f(n)! = f(n) f(n- 1) \dots f(2) f(1) = \prod_{k = 1}^n f(k)$

Do not confuse this with something like the usual $3! = 3 \cdot 2 \cdot 1 = 6$. For the purposes of this paper the notation $(2n)! \equiv (2n) \cdot (2(n -1)) \dots 2 \cdot 1 = 2^n n!$ rather than $(2n)! = (2n) \cdot (2n – 1) \dots 2 \cdot 1$. This notation is standard.

Back to the problem.

$g(n) = A \left ( -\dfrac{1}{3} \right )^{n-1} (n – 1)!$

So, since $h_n = g(n)$,

$h_n = g(n) = A \left ( -\dfrac{1}{3} \right )^{n-1} (n – 1)!$

The method for finding the particular solution for a general linear recursion will be described below. Here I will instead use a somewhat advanced technique called Difference Calculus and we’ll talk about how to generate a particular solution in another example.

We start by multiplying both sides by an unknown function d(n), which we will be able to define away later.

$d(n) ~ n p_n + d(n) ~ 3 p_{n + 1} = d(n) \dfrac{1}{n + 1}$

Now let

$c(n + 1) = 3 d(n)$

$-c(n) = n d(n)$

That allows us to rewrite the recursion as

$-c(n) p_n + c(n + 1) p_{n + 1} = \dfrac{d(n)}{n + 1}$

The LHS has a simple expression in Difference Calculus. The forward difference operator, $\Delta$, is defined as $\Delta f(n) = f(n + 1) – f(n)$. It is similar to the derivative operator in Calculus and its inverse is likewise similar to an integral, in this case, it is a summation.

$\Delta (c(n) p_n) = \dfrac{d(n)}{n + 1}$

$\Delta ^{-1} \Big ( \Delta (c(n) p_n ) \Big ) = \Delta ^{-1} \left ( \dfrac{d(n)}{n + 1} \right )$

$\displaystyle c(n) p_n = \sum_{j = 1}^{n – 1} \dfrac{d(j)}{j + 1}$

$\displaystyle p_n = \dfrac{1}{c(n)} \sum_{j = 1}^{n – 1} \dfrac{d(j)}{j + 1}$

$\displaystyle p_n = \dfrac{1}{c(n)} \sum_{j = 1}^{n – 1} \dfrac{-c(j)}{j (j + 1)}$

We may find an expression for c(n) by eliminating the d(n) from the equations that define it:

$c(n + 1) = – \dfrac{3}{n} c(n)$

leading to

$c(n) = (-3)^{n – 1} \dfrac{B}{(n – 1)!}$

So

$\displaystyle p_n = \dfrac{(n – 1)!}{(-3)^{n – 1} B} \sum_{j = 1}^{n – 1} (-1) \dfrac{1}{j (j + 1)} \dfrac{ (-3)^{j – 1}B}{(j – 1)!}$

After some simplification

$\displaystyle p_n = – \left ( – \dfrac{1}{3} \right )^{n-1} (n-1)! \sum_{j=1}^{n-1} \dfrac{ (-3)^{j-1} }{ (j+1)! }$

Note that there is no closed-form expression for the particular solution. This is fairly common.

So finally, the solution to Eq. 1.1 is

$\displaystyle a_n = \left ( – \dfrac{1}{3} \right )^{n-1} (n-1)! \left ( A – \sum_{j=1}^{n-1} \dfrac{ (-3)^{j-1} }{ (j+1) } \right )$

We may easily generalize this process to the general linear inhomogeneous first-order recursion equation $b_0(n) a_n + b_1(n) a_{n + 1} = \beta (n)$. The solution to this recursion is

$\displaystyle a_{n} = (-1)^{n-1}\dfrac{b_{0}(n-1)!}{b_{1}(n-1)!}\left(A+\sum_{j=1}^{n-1}(-1)^{j}\dfrac{b_{1}(j-1)!}{b_{0}(j)!}\beta(j)\right)$

Second Order Homogeneous Recursions

Solve

$(2.1)~~ 2a_n – 3 a_{n + 1} + a_{n + 2} = 0$

Let

$f(n) a_n + a_{n + 1} = g(n)$

We can find what the auxiliary functions f(n) and g(n) are by the following procedure.

$a_{n + 1} = -f(n) a_n + g(n)$

$a_{n + 2} = -f(n + 1) a_{n + 1} + g(n + 1) = -f(n + 1) \Big ( -f(n) a_n + g(n) \Big ) + g(n + 1)$

or

$a_{n + 2} = f(n + 1) f(n) a_n – f(n + 1) g(n) + g(n + 1)$

Putting this into our recursion gives:

$\begin{array}{ll} (2.2) & \begin{array}{l} -3 g(n) – f(n + 1) g(n) + g(n +1) = 0 \\ 2 + 3 f(n) + f(n+1) f(n) = 0 \end{array} \end{array}$

where the first equation comes from equating the constants and the second by equating the coefficients of the $a_n$ terms.

It is not necessary, but useful, to take f(n) = f = constant, so solving the second equation gives $f = \{-1, -2 \}$. We will use

f = -1 in what follows. The first equation becomes

$-3 g(n) + g(n) + g(n + 1) = 0$

which gives

$g(n) = A 2^n$

Thus we need to solve

$-a_n + a_{n + 1} = A 2^n$

This is a first-order inhomogeneous recursion, which we already have the solution for in Section 2, Eq. 2.7. So finally, the solution to Eq. 2.1 is

$\displaystyle a_n = (-1)^{n-1} (-1)^{n-1} \left ( B + A \sum_{j=1}^{n-1} (-1)^j \dfrac{1}{(-1)^j} 2^{j-1} \right ) = B + A \dfrac{1}{2} (2^n – 2)$

which we may rewrite more simply as $a_n = B + A 2^n$.

Equivalence of Solutions Using Different f(n) Functions

In the last example, we arbitrarily chose f = -1 to generate the solution. We now use f = -2 and show that both solutions are the same. From Eqs. 2.2 we have

$-3 g(n) + 2 g(n) + g(n + 1) = 0$

So g(n) = B. Thus we need to solve

$-2 a_n + a_{n +1} = B$

and we get

$\displaystyle a_n = (-1)^{n-1} (-2)^{n-1} \left ( B + A \sum_{j = 1}^{n – 1} \left ( \dfrac{1}{2} \right )^j \right )$

which may again be rewritten as $a_n = B + A 2^n$.

Second Order Homogeneous Recursions (II)

Solve

$(3.1)~~n(n+2) a_n + (4n + 9) a_{n+1} + 3 a_{n+2} = 0$

Let $f(n) a_n + a_{n + 1} = g(n)$. By the same process as above:

$\begin{array}{l} (4n + 9) g(n) – 3 f(n + 1) g(n) + 3 g(n + 1) = 0 \\ n(n + 2) – (4n + 9) f(n) + 3 f(n + 1) f(n) = 0 \end{array}$

Note that we may take f(n) = n + 3 from the second equation. Thus

$(4n + 9) g(n) – 3(n + 3) g(n) + 3 g(n + 1) = 0$

so we may define

$g(n) = A (-3)^{-n} (n – 1)!$

We need to solve $(n + 2) a_n + a_{n + 1} = A (-3)^{-n} (n – 1)!$. This is a first-order homogeneous linear recursion and may be solved using the general formula given in section 1.

$\displaystyle a_n = (-1)^n (n + 1)! \left ( B + A \sum_{j = 1}^{n -1} \dfrac{3^{-j}}{j(j + 1)(j + 2)} \right )$

We may similarly solve the general linear homogenous second order recursion equation $b_0(n) a_n + b_1(n) a_{n + 1} + b_2(n) a_{n + 2} = 0$.  The solution is

$\displaystyle a_n = (-1)^{n – 1} f(n – 1)! \left ( A + B \sum_{j = 1}^{n – 1} \dfrac{b_0(j – 1)!}{b_2(j – 1)! f(j – 1)! f(j)!} \right )$

Second Order Inhomogeneous Recursions

Solve

$(4.1) ~~4 a_n + 4 a_{n + 1} + a_{n + 2} = 5$

We start by solving the homogeneous recursion: $4 h_n + 4 h_{n +1} + h_{n +2} = 0$. Let $f(n) h_n + h_{n + 1} = g(n)$.

$\begin{array}{l} 4 g(n) – f(n + 1) g(n) + g(n + 1) = 0 \\ 4 – 4 f(n) + f(n + 1) f(n) = 0 \end{array}$

We may again take f(n) = f = constant. Thus f = 2 and $g(x) = A(-2)^{n – 1}$. So we need to solve the linear recursion

$2 h_n + h_{n +1} = A ( -2)^{n – 1}$

Using the general formula for the solution of a linear recursion above gives

$\displaystyle h_n = (-1)^{n – 1} 2^{n – 1} \left ( B + A \sum_{j = 1}^{n -1} (-1)^j \dfrac{1}{2^j} \right ) = (-2)^{n – 1}( B + A(n – 1)$

We will redefine A and B so that $n = B(-2)^n + An(-2)^n = (An + B) (-2)^n$ for convenience.

To find a particular solution we note that if we set $\displaystyle p_n = h’_n \sum_{j = 1}^{n – 1} q_j \beta (j)$, where $h’_n$ is an example of a homogeneous solution and $\beta (j)$ the inhomogeneous term, we may write a recursion to solve for the $q_j$: Any form of the homogeneous solution will do to generate a particular solution so we may choose $h’_n = (-2)^n$.

$\displaystyle p_n = h’_n = \sum_{j = 1}^{n – 1} q_j \beta (j) = 5 h’_n \sum_{j = 1}^{n – 1} q_j$

Inserting this into Eq. 4.1 gives

$(4 h’_{n +1} + h’_{n +2} ) q_n + h’_{n + 2} q_{n + 1} = 1$

$-4 (-2)^n q_n + 4 (-2)^n q_{n + 1} = 1$

$-q_n + q_{n + 1} = \dfrac{1}{4} ( -2)^{-n}$

which is, again, the first-order recursion. The solution for $q_n$ may be written as

$\displaystyle q_n = C + \dfrac{1}{4} \sum_{k = 1}^{n – 1} (-2)^{-k}$

$q_n = C – \dfrac{1}{12} ( 1 + 2 (-2)^{-n} )$

Thus

$\displaystyle p_n = 5 (-2)^{-n} \sum_{j = 1}^{n – 1} \left ( C – \dfrac{1}{12} ( 1 + 2 (-2)^{-j} ) \right )$

$p_n = \left( 5 C(n – 1) – \dfrac{5}{36}(3n – 5) \right ) (-2)^n + \dfrac{5}{9}$

Note that the first term is equivalent to a general homogeneous solution, so we may drop it from the particular solution and define $p’_n = \dfrac{5}{9}$. Thus the solution to Eq. 3.1 is

$a_n = (An + B) (-2)^n + \dfrac{5}{9}$

Third Order Homogeneous Recursions

Solve

$(5.1) ~~12 a_n + 28 a_{n +1} + 19 a_{n + 2} + 4 a_{n +3} = 0$

Let $f_0 a_n + f_1 a_{n + 1} + a_{n +2} = g(n)$.

By a similar derivation given for the second-order auxiliary functions we may derive:

$\begin{array}{l} 19 g(n) – 4 f_1 g(n) + 4 g(n + 1) = 0 \\ 12 – 19 f_0 + 4 f_1 f_0 = 0 \\ 28 – 19 f_1 – 4 f_0 + 4 f_1^2 = 0 \end{array}$

The solutions are$(f_0, f_1) = \{(4, 4), (3/2, 11/4) \}$. We will use $(f_0, f_1) = (4 ,4)$ but the other solution may be shown to give the same result.

$19 g(n) – 16 g(n) + 4 g(n + 1) = 0$

$g(n) = A \left ( – \dfrac{3}{4} \right )^n$

So we need to solve

$(5.2) ~~4 a_n + 4 a_{n + 1} + a_{n + 2} = A \left ( – \dfrac{3}{4} \right ) ^n$

Let $4 h_n + 4 h_{n + 1} + h_{n + 2} = 0$. We find that the homogeneous solution may be written as $h_n = (Cn + B) (-2)^n$.

For the particular solution let

$\displaystyle p_n = h’_n \sum_{j = 1}^{n – 1} q_j A \left ( – \dfrac{3}{4} \right )^j$, with $h’_n = (-2)^n$

Inserting this into Eq. 5.2 gives

$\displaystyle 4h’_n \sum_{j = 1}^{n – 1} q_j A \left ( – \dfrac{3}{4} \right )^j + 4 h’_{n + 1} \sum_{j = 1}^{n} q_j A \left ( – \dfrac{3}{4} \right )^j + h’_{n +2} \sum_{j = 1}^{n + 1} q_j A \left ( – \dfrac{3}{4} \right )^j = A \left ( – \dfrac{3}{4} \right )^n$

and after some simplification

$4 q_n + 3 q_{n +1} = – (-2)^n$

This is a first-order recursion and has the solution

$q_n = \dfrac{5}{20} D \left ( – \dfrac{8}{6} \right )^n + \dfrac{5}{20} \left ( – 8 \left ( – \dfrac{1}{2} \right )^n + 3 \left ( – \dfrac{8}{6} \right )^n \right )$

Inserting this into $p_n$ we write the solution as

$p_n = A \left ( – \dfrac{3}{4} \right )^n + \text{copy of homogeneous solution}$

So we may take $p’_n = A \left ( – \dfrac{3}{4} \right )^n$ and, finally, the solution to Eq. 5.1 is

$a_n = A \left ( – \dfrac{3}{4} \right )^n + (Cn + B) (-2)^n$

First Order Inhomogeneous Differential Equations

We may easily extend this method to Linear Differential Equations.

Solve

$(6.1)~~\dfrac{1}{x} y + 2 y’ = \dfrac{5}{3} x$

Let $\dfrac{1}{2} h + 2 h’ = 0$. Define h = g(x). Thus

$\dfrac{1}{x} g(x) + 2 g'(x) = 0$

This has the solution

$\displaystyle h = g(x) = Exp \left [ \int ^x – \dfrac{1}{2x} ~ dx \right ] = A e^{-(1/2)~ln(x)} = \dfrac{A}{\sqrt{x}}$

For the particular solution, let $\displaystyle p = \dfrac{1}{\sqrt{x}} \int ^x q(x) \dfrac{5}{3} x ~ dx$.

Inserting this into Eq. 6.1 gives.

$\displaystyle \dfrac{5}{3x} x^{-1/2} x ~q(x)~ dx + 2 \cdot \dfrac{-5}{6} x^{-3/2} \int ^x x ~ q(x) ~ dx + \dfrac{10}{3} x^{1/2} q(x) = \dfrac{5}{3} x$

or

$q(x) = \dfrac{1}{2} x^{1/2}$

So

$\displaystyle p = x^{-1/2} \int ^x \dfrac{1}{2} x^{1/2} \cdot \dfrac{5}{3} x ~ dx = \dfrac{1}{3} x^2 + \dfrac{5}{6} C x^{-1/2}$

The second term is a copy of the homogeneous solution so we may discard it. That leaves $p(x) = \dfrac{1}{3} x^2$ giving the final solution to Eq. 6.1 to be

$y(x) = \dfrac{A}{\sqrt{x}} + \dfrac{1}{3} x^2$

Second Order Homogeneous Differential Equations

Solve

$(7.1) ~~ y + x y’ + y” = 0$

Let$f(x) y + y’ = g(x)$. The derivation of the auxiliary function equations is similar to the recursion derivation. The main difference is that we solve for f(x) and g'(x) instead of f(n + 1) and g(n + 1). An extra term in f'(x) appears in the second equation, but this gives no great extra difficulty.

$\begin{array}{l} x g(x) – f'(x) g(x) + g'(x) = 0 \\ -x f(x) – f(x) + f^2(x) = 0 \end{array}$

The solution to the second equation is f(x) = x, so the first equation becomes

$x g(x) – x g(x) + g'(x) = 0$

$g(x) = A$

So we need to solve $x y + y’ = A$. This is a first-order differential equation that gives the solution to Eq. 7.1 to be

$\displaystyle y(x) = B e^{x^2/2} + A e^{x^2/2} \int ^x e^{x^2/2} ~ dx$