This isn’t meant as a full introduction to recursion relations but it surely ought to suffice for nearly any stage of the coed.

Most of us keep in mind recursion relations from secondary college. We begin with a quantity, say, 1. Then we add 3. That provides us 4. Now we that quantity and add 3 once more and get 7. And so forth. This course of creates a collection of numbers ##{ 1, 4, 7, 10, dots }##. As soon as we get past that stage we begin speaking about signify these. Properly, let’s name the beginning quantity ##a_0##. Then the subsequent quantity within the collection can be ##a_1##, then ##a_2##, …, on to ##a_n## the place n is the nth quantity within the collection. We could now specific our recursion as a rule: ##a_{n +1} = a_n + 3##, the place ##a_0 = 1##.

We could go a lot additional. We are able to speak about issues just like the Fibonacci collection: ##F_{n + 2} = F_{n + 1} + F_{n}##, the place ##F_1 = F_2 = 1##. That is the well-known collection ##{ 1, 1, 2, 3, 5, 8, 13, dots }##. However what if we wish a formulation to search out out what ##F_n## is for the nth quantity within the collection? That is the aim of this paper. As a pleasant facet impact, it seems that the tactic introduced right here could be utilized to Differential Equations as effectively, which places it squarely within the focus of Physics and Engineering. I will likely be spending more often than not speaking about recursions, that are easier to use, however I’ll make sure that to incorporate a number of examples of Differential Equations to point out how that’s performed as effectively.

What I’m calling “discount of order” is a technique comparable in idea to, however not fairly the identical as, the tactic utilized in Differential Equations. The concept is to take an mth order homogeneous recursion and scale back it to an m-1th order inhomogeneous recursion which, in principle, ought to be simpler to unravel. In Differential Equations, it’s typical to be given an answer to the unique equation and derive one other answer primarily based on that. This methodology doesn’t use that step.

What follows is a collection of examples that may make the tactic clear.

First Order Homogeneous Recursions

This instance goes to be a bit lengthy however I must level out a number of ideas on the best way.

Resolve

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

The recursion is linear so we could put ##a_n = h_n + p_n##. We begin by fixing the homogeneous recursion

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

Now we scale back the order. We need to write a brand new, inhomogeneous, recursion of 1 order decrease that has the identical answer, with a number one coefficient of 1. On 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} proper )!##

the place f(n)! is a “useful factorial” outlined as

##displaystyle f(n)! = f(n) f(n- 1) dots f(2) f(1) = prod_{ok = 1}^n f(ok)##

Don’t confuse this with one thing like the same old ##3! = 3 cdot 2 cdot 1 = 6##. For the needs of this paper the notation ##(2n)! equiv (2n) cdot (2(n -1)) dots 2 cdot 1 = 2^n n!## moderately than ##(2n)! = (2n) cdot (2n – 1) dots 2 cdot 1##. This notation is commonplace.

Again to the issue.

##g(n) = A left ( -dfrac{1}{3} proper )^{n-1} (n – 1)!##

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

##h_n = g(n) = A left ( -dfrac{1}{3} proper )^{n-1} (n – 1)!##

The strategy for locating the actual answer for a basic linear recursion will likely be described beneath. Right here I’ll as a substitute use a considerably superior approach known as Distinction Calculus and we’ll speak about generate a selected answer in one other instance.

We begin by multiplying either side by an unknown operate d(n), which we will outline 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 permits 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 easy expression in Distinction Calculus. The ahead distinction operator, ##Delta##, is outlined as ##Delta f(n) = f(n + 1) – f(n)##. It’s just like the by-product operator in Calculus and its inverse is likewise just like an integral, on this case, it’s a summation.

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

##Delta ^{-1} Massive ( Delta (c(n) p_n ) Massive ) = Delta ^{-1} left ( dfrac{d(n)}{n + 1} proper )##

##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 could discover an expression for c(n) by eliminating the d(n) from the equations that outline it:

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

resulting in

##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} proper )^{n-1} (n-1)! sum_{j=1}^{n-1} dfrac{ (-3)^{j-1} }{ (j+1)! }##

Notice that there is no such thing as a closed-form expression for the actual answer. That is pretty widespread.

So lastly, the answer to Eq. 1.1 is

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

We could simply generalize this course of to the final linear inhomogeneous first-order recursion equation ##b_0(n) a_n + b_1(n) a_{n + 1} = beta (n)##. The answer 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)proper)##

Second Order Homogeneous Recursions

Resolve

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

Let

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

We are able to discover what the auxiliary capabilities f(n) and g(n) are by the next process.

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

##a_{n + 2} = -f(n + 1) a_{n + 1} + g(n + 1) = -f(n + 1) Massive ( -f(n) a_n + g(n) Massive ) + g(n + 1)##

or

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

Placing this into our recursion offers:

##start{array}{ll} (2.2) & start{array}{l} -3 g(n) – f(n + 1) g(n) + g(n +1) = 0 2 + 3 f(n) + f(n+1) f(n) = 0 finish{array} finish{array}##

the place the primary equation comes from equating the constants and the second by equating the coefficients of the ##a_n## phrases.

It isn’t mandatory, however helpful, to take f(n) = f = fixed, so fixing the second equation offers ##f = {-1, -2 }##. We are going to use

f = -1 in what follows. The primary equation turns into

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

which provides

##g(n) = A 2^n##

Thus we have to remedy

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

It is a first-order inhomogeneous recursion, which we have already got the answer for in Part 2, Eq. 2.7. So lastly, the answer 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} proper ) = B + A dfrac{1}{2} (2^n – 2)##

which we could rewrite extra merely as ##a_n = B + A 2^n##.

Equivalence of Options Utilizing Totally different f(n) Features

Within the final instance, we arbitrarily selected f = -1 to generate the answer. We now use f = -2 and present that each options are the identical. From Eqs. 2.2 we’ve

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

So g(n) = B. Thus we have to remedy

## -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} proper )^j proper )##

which can once more be rewritten as ##a_n = B + A 2^n##.

Second Order Homogeneous Recursions (II)

Resolve

##(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 identical course of as above:

## start{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 finish{array}##

Notice that we could 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 could outline

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

We have to remedy ##(n + 2) a_n + a_{n + 1} = A (-3)^{-n} (n – 1)!##. It is a first-order homogeneous linear recursion and could also be solved utilizing the final formulation given in part 1.

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

We could equally remedy the final 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 answer 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)!} proper )##

Second Order Inhomogeneous Recursions

Resolve

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

We begin by fixing the homogeneous recursion: ##4 h_n + 4 h_{n +1} + h_{n +2} = 0##. Let ##f(n) h_n + h_{n + 1} = g(n)##.

##start{array}{l} 4 g(n) – f(n + 1) g(n) + g(n + 1) = 0 4 – 4 f(n) + f(n + 1) f(n) = 0 finish{array}##

We could once more take f(n) = f = fixed. Thus f = 2 and ##g(x) = A(-2)^{n – 1}##. So we have to remedy the linear recursion

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

Utilizing the final formulation for the answer of a linear recursion above offers

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

We are going to redefine A and B in order that ##n = B(-2)^n + An(-2)^n = (An + B) (-2)^n## for comfort.

To discover a explicit answer we word that if we set ##displaystyle p_n = h’_n sum_{j = 1}^{n – 1} q_j beta (j)##, the place ##h’_n## is an instance of a homogeneous answer and ##beta (j)## the inhomogeneous time period, we could write a recursion to unravel for the ## q_j##: Any type of the homogeneous answer will do to generate a selected answer so we could select ##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 offers

##(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, once more, the first-order recursion. The answer for ##q_n## could also be written as

##displaystyle q_n = C + dfrac{1}{4} sum_{ok = 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} ) proper )##

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

Notice that the primary time period is equal to a basic homogeneous answer, so we could drop it from the actual answer and outline ##p’_n = dfrac{5}{9}##. Thus the answer to Eq. 3.1 is

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

Third Order Homogeneous Recursions

Resolve

##(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 an identical derivation given for the second-order auxiliary capabilities we could derive:

##start{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 finish{array}##

The options are## (f_0, f_1) = {(4, 4), (3/2, 11/4) }##. We are going to use ##(f_0, f_1) = (4 ,4)## however the different answer could also be proven to provide the identical consequence.

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

##g(n) = A left ( – dfrac{3}{4} proper )^n##

So we have to remedy

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

Let ##4 h_n + 4 h_{n + 1} + h_{n + 2} = 0##. We discover that the homogeneous answer could also be written as ##h_n = (Cn + B) (-2)^n##.

For the actual answer let

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

Inserting this into Eq. 5.2 offers

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

and after some simplification

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

It is a first-order recursion and has the answer

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

Inserting this into ##p_n## we write the answer as

##p_n = A left ( – dfrac{3}{4} proper )^n + textual content{copy of homogeneous answer}##

So we could take ##p’_n = A left ( – dfrac{3}{4} proper )^n## and, lastly, the answer to Eq. 5.1 is

##a_n = A left ( – dfrac{3}{4} proper )^n + (Cn + B) (-2)^n##

First Order Inhomogeneous Differential Equations

We could simply prolong this methodology to Linear Differential Equations.

Resolve

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

Let ##dfrac{1}{2} h + 2 h’ = 0##. Outline h = g(x). Thus

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

This has the answer

##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 actual answer, let ##displaystyle p = dfrac{1}{sqrt{x}} int ^x q(x) dfrac{5}{3} x ~ dx##.

Inserting this into Eq. 6.1 offers.

##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 time period is a duplicate of the homogeneous answer so we could discard it. That leaves ##p(x) = dfrac{1}{3} x^2## giving the ultimate answer to Eq. 6.1 to be

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

Second Order Homogeneous Differential Equations

Resolve

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

Let## f(x) y + y’ = g(x)##. The derivation of the auxiliary operate equations is just like the recursion derivation. The principle distinction is that we remedy for f(x) and g'(x) as a substitute of f(n + 1) and g(n + 1). An additional time period in f'(x) seems within the second equation, however this provides no nice further problem.

##start{array}{l} x g(x) – f'(x) g(x) + g'(x) = 0 -x f(x) – f(x) + f^2(x) = 0 finish{array}##

The answer to the second equation is f(x) = x, so the primary equation turns into

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

##g(x) = A##

So we have to remedy ##x y + y’ = A##. It is a first-order differential equation that provides the answer 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##