Question 2: The Fibonacci numbers are defined as follows: f₀ = 0, f₁ = 1, and F_n = F_n-1 + F_n-2 for n >=2, Prove each of the following three claims: 

• For each n >=0, f_3n is even.
• For each n >= 0, f3n+1 is odd.
•  For each n >= 0, f3n+2 is odd.  

Question 3: 

is equal to the nth Fibonacci number fn. Since the Fibonacci numbers are obviously integers, the number in (1) is an integer as well. 

Prove that the number in (1) is an integer using only Newton's Binomial Theorem. 

Question 4: Question 4: Let n >= 1 be an integer and consider a 2Xn board Bn consisting of 2n cells, each one having sides of length one. The top part of the figure below shows B₁₃. 

A brick is a horizontal or vertical board consisting of 2 cells; see the bottom part of the

figure above. A tiling of the board Bn is a placement of bricks on the board such that 

 _ the bricks exactly cover Bn and

_ no two bricks overlap. 

The figure below shows a tiling of B₁₃. 

Question 5: We consider strings of n characters, each character being a, b, c, or d, that contain an even number of as. (Recall that 0 is even.) Let E_n be the number of such strings. Prove that for any integer n >= 1, E_n+1=  2. E_n + 4ⁿ 

Question 6: Let an be the number of bit strings that contain 000. Prove that for n >= 4,

An = a_n+1 + a_n+2 + a_n+3 + 2^n-3

Question 7: A binary tree is

_   Either one single node

_ or a node whose left subtree is a binary tree and whose right subtree is a binary tree. 

Prove that any binary tree with n leaves has exactly 2n ?? 1 nodes. 

Question 8: Let S be a set of n points in the plane. Each point p of S is given by its x-and y-coordinates px and py, respectively. We assume that no two points of S have the same x-coordinate and no two points of S have the same y-coordinate. 

A point p of S is called maximal in S if there is no point in S that is to the north-east of p, i.e., 

{ q (- S : qx > px and qy > py } = Ø 

The figure below shows an example, in which the O_-points are maximal and the _-points are not maximal. Observe that, in general, there is more than one maximal element in S. 

Describe a recursive algorithm MaxElem(S) that has the same basic structure as algorithm Merge Sort that we have seen in class, and that does the following:

Input: A set S of n points in the plane, in sorted order from left to right. Output: All maximal elements of S, in sorted order from left to right.

The running time T(n) of your algorithm must be O(n log n). Derive a recurrence for T(n). (You do not have to solve the recurrence, because we have done that in class.) You may assume that n is a power of 2.

Question 9: For an integer n >= 1, draw n straight lines, such that no two of them are parallel and no three of them intersect in one single point. These lines divide the plane into regions (some of which are bounded and some of which are unbounded). Denote the number of these regions by R_n. Derive a recurrence for the numbers R_n and use it to prove that for n >= 1,

R_n = 1 + n(n + 1)=2: