Week 9 - Recurrence relations and networks

Sunday, 21 April 2019

12:51 AM

A recurrence relation of order k is of the form where , Ck are constant and f(n) is a function of n. To fully determine the solution, a recurrence relation of order k must also have k initial conditions. When k = 1 this is a first order recurrence relation, which we explored in the previous question. When k = 2 this is called a second order recurrence relation. a) Consider the homogenous second order recurrence relation xn — + = 0 forn > 0 with initial condition xo arrange the relation into the form :r.n = — to find 68 336 1672 8344 . Gap 1 3 and = 14. Re- Submit part Your answer is numerically correct. You were awarded 0.25 marks. Gap 2 Your answer is numerically correct. You were awarded 0.25 marks. Gap 3 Your answer is numerically correct. You were awarded 0.25 marks. Gap 4 Your answer is numerically correct. You were awarded 0.25 marks. You scored 1 mark for this part.

 

b) The n'th term of a second order homogenous recurrence relation can be expressed in the form This is also called the homogenous solution. What are the values for Al and Give answer using the NUMBAS syntax for set. Show steps (Your score will not be affected.) {2,5} Answer. set (2, S) Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

c) The n'th term of a second order non-homogenous recurrence relation can be expressed in the form where hr, is the homogenous solution, and pn is the non-homogenous solution. The sum of the homogenous and non-homogenous solutions is also called the solution to the recurrence relation. Find the solution to the non-homogenous second order recurrence relation with initial condition xo = 3 and = 14. 12n 47 Again, there is no single method to find pn, and so we must 'guess and check'. Suppose pn is a solution to the non-homogenous equation: Pn — 7pn_1 + IOpn_2 = 12n — 47. Since the non-homogenous part f(n) = 12n — 47 is a degree one polynomial, we 'guess' thatpn = an + b for some constants a and b: 12n — 47. This can be simplified to find the values of a and b. The value of a is Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

The value of b is Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. The final step is to apply the initial conditions and discover the values of A and B. When n Score: 1/1 Answered 0: and when n 1: 1-4 — PI = + _BA2 a b These equations can be solved simultaenouslyto find the values of A and B. If = 2then the value of A is Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

The value of Bis Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered The answer is then where a, b Aand B have the values determined above. (Your score will not be affected.) Hide steps Answer: 4 *2An+SAn+3n-2 4 X 211 + 5 2 Submit part You revealed the steps. Your answer is numerically correct. You were awarded 4 marks. Because you received full marks for the part, your answers to the steps aren't counted. You scored 4 marks for this pan.

 

There are two exceptional cases to be careful of when studying recurrence relations: 1. A recurrence of order k must have k independent solutions, and 2. A non-homogenous solution has to be independent of the homogenous solutions. In both cases, an independent solution can be created by mutiplyinga dependent solution by n. a) The homogenous solution to the recurrence relation 12Tn-1 + 35xn_2 = Which shape should you guess for the non-homogenous solution? Opn=C7" opn = cn27" = cn7n 7n Submit part You chose a correct answer. You were awarded 1 mark. You scored 1 mark forthis part. Score: 1/1 Answered

 

b) What is the homogenous solution to the recurrence relation @her-I Ohn Submit part You chose a correct answer. You were awarded 1 mark. You scored 1 mark forthis part. Score: 1/1 Answered

 

c) What shape would you guess for the the non-homogenous solution to C5n Cn5n @pn Cn25" Submit part You chose a correct answer. You were awarded 1 mark. You scored 1 mark forthis part. Score: 1/1 Answered

 

A graph is defined to be a set of vertices V and a set of edges E which connect the vertices. For example, consider the graph G = (V, E) where: • {[1,2] A visual representation of the graph G is presented below. Feel free to move the vertcies around to untangle the edges. Two vertices are said to be adjacent if there is an edge between them. What is the set of vertices which are adjacent to vertex 3? Recall that the NUMBAS syntax for the set {0, 1} is set (S, 6, 1) Submit part Your answer is numerically correct. You were awarded 1 mark.

 

b) The degree of a vertex is number of adjacent vertices. Fill out the table of vertex degrees. vertex 1 2 3 4 5 6 Submit part

 

In graph theory, a pathof length n is a list ofn edges [el, e2, , enl such that ei and ei+l share a common vertex forl i < n. For example is a path of length 3 which starts at 1 and ends at 5. A cycle is a special kind of path which starts and ends at the same vertex. Use the checkboxes below to draw a cycle which passes through all of the 5 vertices. This is called the cycle graph C5. Click the edges to form C5. [1,2] [1,5] [2,3] [3,4]

 

A graph G = (V, E) is said to be bipartite ifthe vertex set V can be partitioned into two disjoint sets VI and V2 such that the edges are only between VI and 14, which is to say there are no edges from VI to VI and no edges from 14 to V2. For example, in the graph below the vertex set can be partitioned into the black vertices VI = {1, 2, 3} and the red vertices V2 = {4, 5}. In fact because every vertex in VI is connected to everyvenex in V2 this graph is called the complete bipartite graph The numbers 3 and 2 referto the respective sizes of VI and V2. a) How many edges are in the complete bipartite graph K3,6? 18 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

b) Consider the graph G (V, E) below. Show that G is a bipattite graph by finding a partition ofthe vertex set V = {1, 2, 3, 4, 5, 6, 7, 8, 9} into disjoint subsets VI and 14, such that each edge is only between VI and 14. You may find it helpful to rearrange the graph by draging points. Remember the NUMBAS syntax for the set {0, 2} is VI = set set (3, 8, 9) Submit part Gap 1 There are two possible choices for VI, and this is one ofthem. You were awarded 2 marks. Gap 2 VlcupV2 = V, this isa partition of V. You were awarded 2 marks. You scored 4 marks for this pan. Score: 4/4 Answered

 

 

Created with Microsoft OneNote 2016.