Discount of Order For Recursions

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

Most of us keep in mind recursion relations from secondary faculty. We begin with a quantity, say, 1. Then we add 3. That offers 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 the best way to characterize these. Effectively, let’s name the beginning quantity ##a_0##. Then the following 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 might now categorical our recursion as a rule: ##a_{n +1} = a_n + 3##, the place ##a_0 = 1##.

We might go a lot additional. We will discuss 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 would like a system 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 aspect impact, it seems that the strategy introduced right here might be utilized to Differential Equations as nicely, which places it squarely within the focus of Physics and Engineering. I will probably be spending more often than not speaking about recursions, that are easier to use to, however I’ll ensure that to incorporate a number of examples of Differential Equations to point out how that’s carried out as nicely.

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

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

First Order Homogeneous Recursions

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

Clear up

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

The recursion is linear so we might 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 wish to write a brand new, inhomogeneous, recursion of 1 order decrease that has the identical resolution, 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 “practical factorial” outlined as

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

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!## relatively than ##(2n)! = (2n) cdot (2n – 1) dots 2 cdot 1##. This notation is normal.

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 resolution for a basic linear recursion will probably be described beneath. Right here I’ll as a substitute use a considerably superior method referred to as Distinction Calculus and we’ll discuss the best way to generate a selected resolution in one other instance.

We begin by multiplying each side by an unknown perform d(n), which we can 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 enables 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 much like the by-product operator in Calculus and its inverse is likewise much like an integral, on this case, it’s a summation.

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

##Delta ^{-1} Large ( Delta (c(n) p_n ) Large ) = 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 might 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)! }##

Be aware that there isn’t any closed type expression for the actual resolution. 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 might simply generalize this course of to the overall 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

Clear up

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

Let

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

We will 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) Large ( -f(n) a_n + g(n) Large ) + 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 provides:

##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 needed, however helpful, to take f(n) = f = fixed, so fixing the second equation provides ##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 resolve

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

This can be 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 might 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 now have

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

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

## -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)

Clear up

##(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}##

Be aware that we might 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 might outline

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

We have to resolve ##(n + 2) a_n + a_{n + 1} = A (-3)^{-n} (n – 1)!##. This can be a first-order homogeneous linear recursion and could also be solved utilizing the overall system 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 might equally resolve the overall 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

Clear up

##(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 might once more take f(n) = f = fixed. Thus f = 2 and ##g(x) = A(-2)^{n – 1}##. So we have to resolve the linear recursion

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

Utilizing the overall system for the answer of a linear recursion above provides

##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 specific resolution we be aware 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 resolution and ##beta (j)## the inhomogeneous time period, we might write a recursion to unravel for the ## q_j##: Any type of the homogeneous resolution will do to generate a selected resolution so we might 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 provides

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

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

Be aware that the primary time period is equal to a basic homogeneous resolution, so we might drop it from the actual resolution 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

Clear up

##(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 the same derivation given for the second order auxiliary capabilities we might 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 resolution could also be proven to offer the identical outcome.

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

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

So we have to resolve

##(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 resolution could also be written as ##h_n = (Cn + B) (-2)^n##.

For the actual resolution 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 provides

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

This can be 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 resolution}##

So we might 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 might simply lengthen this technique to Linear Differential Equations.

Clear up

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

Inserting this into Eq. 6.1 provides.

##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 replica of the homogeneous resolution so we might discard it. That leaves ##p(x) = dfrac{1}{3} x^2## giving the ultimate resolution to Eq. 6.1 to be

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

Second Order Homogeneous Differential Equations

Clear up

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

Let## f(x) y + y’ = g(x)##. The derivation of the auxiliary perform equations is much like the recursion derivation. The primary distinction is that we resolve 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 offers no nice additional issue.

##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 resolve ##x y + y’ = A##. This can be a first-order differential equation that offers 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##