Non Homogeneous Recurrence Relation In Discrete Mathematics Pdf

Find the general solution of f(n+2)-6f(n+1)+9f(n)=5 3ⁿ , n 0.

Solution Let f(n)=u_n+v_n , with u_n being the general solution of the homogeneous problem and v_n a particular solution.

(a)

Find u_n : The associated characteristic equation ² -6 + 9 =0 has a repeated root =3 with multiplicity 2. Hence the general solution of the homogeneous problem

u_n+2-6u_n+1+9u_n=0 ,   n 0

is u_n = (A+Bn)3ⁿ .

(b)

Find v_n : Since the r.h.s. of the recurrence relation, the nonhomogeneous part, is 5 3ⁿ and 3 is a root of multiplicity 2 of the characteristic equation (i.e. =3, k=0, M=2), we try due to (***) v_n =B₀ ⁿ n^M Cn²3ⁿ : we just need to observe that C3ⁿ is of the form 5 3ⁿ and that the extra factor n² is due to =3 being a double root of the characteristic equation. Thus

5 3n	=	vn+2-6vn+1+9vn
	=	C(n+2)23n+2-6C(n+1)23n+1+9Cn23n
	=	18C3n .

Hence C=5/18 and v_n =(5/18)n²3ⁿ . Therefore our general solution reads

Find the particular solution of

a_n+4-5a_n+3+9a_n+2-7a_n+1 +2a_n=3 , n 0

satisfying the initial conditions a₀ = 2, a₁ = -1/2, a₂ = -5, a₃ = -31/2 .

Solution We first find the general solution u_n for the homogeneous problem. We then find a particular solution v_n for the nonhomogeneous problem without considering the initial conditions. Then a_n=u_n+v_n would be the general solution of the nonhomogeneous problem. We finally make use of the initial conditions to determine the arbitrary constants in the general solution so as to arrive at our required particular solution.

(a)

Find u_n : Since the associated characteristic equation
has the sum of all the coefficients being zero, i.e. 1-5+9-7+2=0, it must have a root =1. After factorising out ( -1) via ⁴-5 ³+9 ²-7 + 2 = ( -1)( ³-4 ²+5 -2), the rest of the roots will come from ³-4 ²+5 -2 =0. Notice that ³-4 ²+5 -2=0 can again be factorised by a factor ( -1) because 1-4+5-2=0. This way we can derive in the end that the roots are
Thus the general solutions for the homogeneous problem is
or simply u_n=A+Bn+Cn²+D2ⁿ because 1ⁿ 1.

(b)

Find v_n : Notice that the nonhomogeneous part is a constant 3 which can be written as 3 1ⁿ when cast into the form of (**), and that 1 is in fact a root of multiplicity 3. In other words, we have in (***) =1, k=0 and M=3. Hence we try a particular solution v_n=En³ 1ⁿ =En³ . The substitution of v_n into the nonhomogeneous recurrence equations then gives, using a formula in the subsection Binomial Expansions in the Preliminary Mathematics at the beginning of these notes,

3	=	vn+4-5vn+3+9vn+2-7vn+1+2vn
	=	E(n+4)3-5E(n+3)3+9E(n+2)3-7E(n+1)3+2En3
	=	E(n3 + 3n2 4+3n 42+43) -5E(n3 + 3n2 3+3n 32+33)
		+ 9E(n3 + 3n2 2+3n 22+23) -7E(n3 + 3n2 1+3n 12+13) + 2En3
	=	-6E ,

i.e. E= -1/2. Hence v_n= -n³/2.

Note Should you find it very tedious to perform the expansions in the above, you could just substitute, say, n=0 into

3 = E(n+4)³-5E(n+3)³+9E(n+2)³-7E(n+1)³+2En³

to obtain readily 3=E4³-5E3³+9E2³-7E=-6E. Incidentally you don't have to substitute n=0; you can in fact substitute any value for n because the equation is valid for all n. Obviously this alternative technique also applys even if there are more than 1 unknowns in the equation; we just need to substitute sufficiently many distinct values for n to collect enough equations to determine the unknowns. The drawback of this technique is that you have to make sure that the form you have proposed for v_n is absolutely correct through the use of the proper theory, otherwise an error in the form for v_n will go undetected in this alternative approach.

(c)

The general solution of the nonhomogenous problem thus read

a_n = u_n + v_n = A + Bn + Cn² + D2ⁿ - n³/2.

(d)

We now ask the solution in (c) to comply with the initial conditions.

Initial Conditions	Induced Equations	Solutions
a0 = 2 a1 = -1/2 a2 = -5 a3 = -31/2	A+D = 2 A+B+C+2D = 0 A+2B+4C+4D = -1 A+3B+9C+8D = -2	A = 3 B = -2 C = 1 D = -1

Hence our required particular solution takes the following final form

a_n = 3 - 2n + n² - n³/2 - 2ⁿ,   n 0 .

Find the general solution of a_n+1-a_n=n2ⁿ+1 for n 0.

Solution

(a)

The general solution for homogeneous problem is u_n=A because the only root of the characteristic equation is ₁=1.

(b)

Since n2ⁿ+1 = 2ⁿ n +1ⁿ is of the form ₁ ⁿ(b₁n+b₀)+ ⁿ ₂ c₀ and ₂=1 is a simple root of the characteristic equation, we try the similar form v_n = 2ⁿ(B+Cn) + Dn for a particular solution. Substiting v_n into the recurrence relation, we have

n2n+1 = vn+1-vn	=	2n+1(B+C(n+1)) + D(n+1) - 2n(B+Cn) - Dn
	=	2n(Cn+B+2C) + D ,

i.e.

2ⁿ ( (C-1)n + (B+2C) ) + (D-1) = 0 .

In order the above equation be identically 0 for all n 0, we require all its coefficients to be 0, i.e.

C-1=0 ,   B+2C=0 ,   D-1=0 .

Hence B=-2, C=1 and D=1 and the particular solution v_n =2ⁿ(n-2)+n.

(c)

The general solution is u_n+v_n and thus reads

a_n = 2ⁿ(n-2)+n+A , n 0 .

Let m and S(n)= i^m for n . Convert the problem of finding S(n) to a problem of solving a recurrence relation.

Solution We first observe

S(n+1)= (n+1)^m + i^m = S(n) + (n+1)^m .

Since the general solution will contain just 1 arbitrary constant, 1 initial condition should suffice. Hence S(n) is the solution of

Non Homogeneous Recurrence Relation In Discrete Mathematics Pdf

Source: https://staff.cdms.westernsydney.edu.au/cgi-bin/cgiwrap/zhuhan/dmath/dm_readall.cgi?page=24

Posted by: wrightcoma1941.blogspot.com

Share this post