Discount of Order For Recursions

This isn’t meant as a full introduction to recursion relations but it surely ought to suffice for almost any degree of the scholar.

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 how you can characterize these. Effectively, let’s name the beginning quantity ##a_0##. Then the subsequent 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 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 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 would like a components 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 tactic introduced right here might be utilized to Differential Equations as effectively, which places it squarely within the focus of Physics and Engineering. I might be spending more often than not speaking about recursions, that are easier to use, however I’ll ensure that to incorporate just a few examples of Differential Equations to indicate how that’s finished as effectively.

What I’m calling “discount of order” is a technique related in idea to, however not fairly the identical as, the tactic 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 resolve. In Differential Equations, it’s typical to be given an answer to the unique equation and derive one other answer based mostly on that. This methodology doesn’t use that step.

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

First Order Homogeneous Recursions

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

Remedy

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

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 might be described under. Right here I’ll as an alternative use a considerably superior method referred to as Distinction Calculus and we’ll speak about how you can generate a specific answer in one other instance.

We begin by multiplying each side by an unknown operate 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} Huge ( Delta (c(n) p_n ) Huge ) = 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 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 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

Remedy

##(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) Huge ( -f(n) a_n + g(n) Huge ) + 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 obligatory, however helpful, to take f(n) = f = fixed, so fixing the second equation offers ##f = {-1, -2 }##. We’ll use

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

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

which supplies

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

Thus we have to clear up

##-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 now we have

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

Remedy

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

Remedy

##(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 clear up the linear recursion

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

Utilizing the overall 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’ll 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 might write a recursion to resolve for the ## q_j##: Any type of the homogeneous answer will do to generate a specific answer 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}##

Be aware that the primary time period is equal to a normal homogeneous answer, so we might 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

Remedy

##(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’ll 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 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 answer}##

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 prolong this methodology to Linear Differential Equations.

Remedy

##(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 replica of the homogeneous answer so we might 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

Remedy

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

Let## f(x) y + y’ = g(x)##. The derivation of the auxiliary operate equations is much like the recursion derivation. The primary distinction is that we clear up for f(x) and g'(x) as an alternative 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 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 clear up ##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##