Transcription of Solutions to Exercises Chapter 4: Recurrence …
{{id}} {{{paragraph}}}
Example: air traffic controller
Solutions to Exercises Chapter 4: Recurrence …
Solutions to ExercisesChapter 4: Recurrence relations and generatingfunctions1(a) There arenseating positions arranged in a line. Prove that the numberof ways of choosing a subset of these positions, with no two chosen positionsconsecutive, isFn+1.(b) If thenpositions are arranged around a circle, show that the number ofchoices isFn+Fn 2forn 2.(a) Proof by induction. Ifg(n)denotes this number, then we haveg(1) =2=F2,g(2) =3=F3. (Forn=2, we cannot occupy both positions; but all otherchoices are possible.) Forn>2, we separate the seating selections into those inwhich the last position is unoccupied and those in which it is occupied. There areg(n 1)of the first kind. If the last position is taken, then the one before it mustbe free, and we have an arbitrary seating plan on the firstn 2 positions; so thereareg(n 2)of these. Henceg(n) =g(n 1) +g(n 2) =Fn+Fn 1=Fn+1,and the inductive step is proved.(b) Consider a particular position on the circle.
Solutions to Exercises Chapter 4: Recurrence relations and generating functions 1 (a) There are n seating positions arranged in a line. Prove that the number
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: