Description

CENG223
Discrete Computational Structures
Homework 3

Question 1
Use mathematical induction to prove the following:
. (1)
Question 2
1. Alice and Bob, being bored by the midterms, decide to play a game. They take turns to pick a positive integer up to and including 41, that has not been picked before by either of them. Whoever picks a number that sums up to 42 with any of the already picked numbers loses the game. If Alice is the first one to pick a number, and if they both play their best strategies, who will win the game?
Show explicitly the use of Pigeonhole Principle in your answers; otherwise, you will not get any points.
2. How many ways are there to pick 3 nonnegative integers that sum up to 5 if the order of the picked numbers does not matter?
3. How many solutions does the equation
x1 + x2 + x3 = 5
have, where x1, x2 and x3 are positive integers?
Question 3
Find ar satisfying (2)
n
(1 − x3)n = X akxk(1 − x)3n−2k. (3)
k=0
1
Question 4
Solve the following recurrence relation with the given initial conditions
an = 4an−1− an−2− 6an−3 + n − 2, n = 3,4,5,… (4)
with a0 = 3.5, a1 = 4.75, a2 = 13.
1 Regulations
1. You have to write your answers to the provided sections of the template answer file given. Other than that, you cannot change the provided template answer file. If a latex structure you want to use cannot be compiled with the included packages in the template file, that means you should not use it.
2. Do not write any other stuff, e.g. question definitions, to answers’ sections. Only write your answers. Otherwise, you will get 0 from that question.
3. Late Submission: Not allowed
5. Newsgroup: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates on a daily basis.
2 Submission
Submission will be done via COW. Download the given template file, “hw3.tex”, when you finish your exam upload the .tex file with the same name to COW.
Note: You cannot submit any other files. Don’t forget to make sure your .tex file is successfully compiled in Inek machines using the command below.
$ pdflatex hw3.tex
2