Discount of Order For Recursions

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

Most of us bear 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 learn how to 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 might now specific our recursion as a rule: ##a_{n +1} = a_n + 3##, the place ##a_0 = 1##.

We might go a lot additional. We will 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 components 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 strategy introduced right here will be utilized to Differential Equations as nicely, which places it squarely within the focus of Physics and Engineering. I can be spending more often than not speaking about recursions, that are less complicated to use, however I’ll be certain that to incorporate just a few examples of Differential Equations to indicate how that’s executed as nicely.

What I’m calling “discount of order” is a technique related 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 concept, 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 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 must level out just a few 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 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 “useful 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 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 resolution for a normal linear recursion can be described under. Right here I’ll as a substitute use a considerably superior approach known as Distinction Calculus and we’ll speak about learn how to generate a specific 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 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 spinoff 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} 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)! }##

Observe that there isn’t a closed-form expression for the actual resolution. 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 might 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 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 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 essential, 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 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’ve

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

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

Observe 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 final components 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 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 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 final components 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 specific resolution we observe 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 resolve for the ## q_j##: Any type of the homogeneous resolution will do to generate a specific 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 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_{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}##

Observe that the primary time period is equal to a normal 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

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

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.

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

Resolve

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

Let## f(x) y + y’ = g(x)##. The derivation of the auxiliary perform equations is just like the recursion derivation. The principle 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 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 resolve ##x y + y’ = A##. This can be 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##