Discount of Order For Recursions

This isn’t meant as a full introduction to recursion relations however it ought to suffice for nearly any stage 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 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 tips on how to characterize these. Properly, let’s name the beginning quantity ##a_0##. Then the following quantity within the collection could 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 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 seek 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 strategy introduced right here may be utilized to Differential Equations as nicely, which places it squarely within the focus of Physics and Engineering. I shall be spending more often than not speaking about recursions, that are easier to use, however I’ll make certain to incorporate a number of examples of Differential Equations to point out how that’s finished 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 concept is to take an mth order homogeneous recursion and scale back it to an m-1th order inhomogeneous recursion which, in idea, needs to be simpler to resolve. 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 technique doesn’t use that step.

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

First Order Homogeneous Recursions

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

Clear up

##(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 “practical 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 standard ##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 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 normal linear recursion shall be described under. Right here I’ll as a substitute use a considerably superior approach referred to as Distinction Calculus and we’ll discuss tips on how to generate a specific answer in one other instance.

We begin by multiplying either 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 spinoff 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 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 isn’t any closed-form expression for the actual answer. That is pretty frequent.

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 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 obligatory, 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 clear up

##-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 Completely 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 clear up

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

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 clear up ##(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 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 could equally clear up 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 could once more take f(n) = f = fixed. Thus f = 2 and ##g(x) = A(-2)^{n – 1}##. So we have to clear up 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 answer 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 answer and ##beta (j)## the inhomogeneous time period, we could write a recursion to resolve for the ## q_j##: Any type of the homogeneous answer will do to generate a specific 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 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, 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 normal 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

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 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 present 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 clear up

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

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 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 answer, 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 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

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 principle distinction is that we clear up 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 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 clear up ##x y + y’ = A##. It is 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##