## CPS420 |
## W2017 Assignment 1 | |

## Worth: 10% |
## Sequences, recursion, and induction |
## Due: Monday February 13 |

## Team SizeThis lab can be done in teams of 1 or 2.## Assignment Description## Part A - Question5.2.32 in textbookYou have two biological parents, four biological grandparents, eight biological grandparents, and so on...- If all your ancestors were distinct, what would be the total number of your ancestors for the past 40 generation counting your parents' generation as number one.
- Assuming that each generation represents 25 years, how long is 40 generations? Explain your answer.
- The total number of people who have ever lived is approximately 10 billion, which equals 10
^{10}. Compare this fact with the answer to part 1. What do you deduce?
## Part B - Based on Question 5.7.52 in textbook:A single line divides a plane into two regions. Two lines can divide it into four regions by crossing each other. Three lines can divide it into seven regions.
When n is a non-negative integer,
let P - Derive a recurrence relation for P
_{k}in terms for P_{k-1}, for all integers k greater or equal to 2. - Use iteration to guess an explicit formula for P
_{n} - Prove by induction that the explicit formula is correct (i.e. that it solves the recurrence relation)
## Part C - Question 5.4.25 in textbookImagine a situation in which eight people, numbered consecutively 1-8, are arranged in a circle. Starting from person #1, every second person in the circle is eliminated. The elimination process continues until only one person remains. In the first round the people numbered 2, 4, 6, and 8 are eliminated; in the second round the people numbered 3, and 7 are eliminated; in the third round person #5 is eliminated. So after the third round only person #1 remains.- Given a set of 16 people arranged in a circle and numbered consecutively 1-16, list the numbers of the people who are eliminated in each round if every second person is eliminated and the elimination process continues until only one person remains. Assume that the starting point is person #1.
- Use mathematical induction to prove that for all integers n >= 1,
given any set of 2
^{n}people arranged in a circle and numbered consecutively from 1 to 2^{n}, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only person #1 will remain. - Use the result of part 2 to prove that for any non-negative integers n and m with 2
^{n}<= 2^{n}+m < 2^{n+1}, if r=2^{n}+m, then given any set of r people arranged and numbered from 1 through r, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only one person #(2m+1) will remain.
## References- Textbook chapter 5.1, 5.2, 5.3, 5.4, 5.6, 5.7
- Handouts and other references can be found in the Lecture Material
## Hand InThis lab is a paper submission to be handed in at the Computer Science office.- Hand in your written solution with a marking sheet (docx or pdf) stapled to the front.
- In addition to the assignment itself you will need to also submit the Assignment 1 Submission Declaration on D2L. This assignment will not be graded unless this declaration has been submitted.
## Solutions |

Last modified Tuesday, 21-Feb-2017 23:40:32 EST