Description
Question 1 (15 points)
Use mathematical induction to prove that for n ∈ N +, 62n − 1 is divisible by both 5 and 7.
Question 2 (20 points)
Let H0 = 1, H1 = 5, H2 = 7, and define
Hn = 8Hn−1 + 8Hn−2 + 9Hn−3,
for any integer n ≥ 3. Use strong induction to show that Hn ≤ 9
n
for n ∈ N.
Question 3 (20 points)
How many bit strings of length 8 contain either 4 consecutive 0s or 4 consecutive 1s?
Question 4 (25 points)
Assume that a small universe has 10 distinct stars and 100 distinct planets so that 20 of them are habitable and 80 of them are nonhabitable by humans. How many ways are there to form a galaxy with
exactly 1 star, 2 habitable planets and 8 nonhabitable planets such that there is at least 6 nonhabitable
planets between the 2 habitable ones?
Note: For this question, a galaxy is a bound system with a star at the center and a group of planets that
orbit the star. Different orders of the planets create different galaxies.
1
Question 5 (20 points)
Suppose that we have a jumping robot in an unlimited corridor which is divided into cells with the same
size as below:
This robot can land one cell away with a jump. With a little boost, it can land two or three cells away
as well.
a. Find a recurrence relation to describe in how many different ways the robot can move to n cells
away from its initial location.
b. What are the initial conditions?
c. How many ways the robot can move to 9 cells away from its initial location?
Regulations
1. Your submission should be a single vector-based PDF document with the name the3.pdf.
2. Late Submission: Not allowed.
3. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be
punished according to the university regulations.
4. Updates & Announcements: You must follow the ODTUClass for discussions and possible updates. You can ask your questions in the Student Forum on the course page in ODTUClass.
5. Evaluation: Your .pdf file will be checked for plagiarism automatically using “black-box” technique and manually by assistants, so make sure to obey the specifications.
Submission
Submission will be done via ODTUClass. For those who prefer to use LATEX to generate the vector-based
PDF file, a template answer file the3.tex is provided in ODTUClass. You need to compile the filled
template yourselves and submit the generated .pdf file only.
2
