Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science February 9, 1995 Professors Mauricio Karchmer and Ron Rivest

Problem Set 1

Due: In recitation, February 17.

Reading: Chapter 1 of Discrete Mathematics for Computer Scientists by J.K. Truss.

Problem 1-1. Let F_{i} be the ith Fibonacci number; that is,

F_{0} = 0, F_{1} = 1, and F_{i} = F_{i−1} + F_{i−2}, for i ≥ 2.

Show that 1 + ∑_{i=0}^{k} F_{i} = F_{k+2} for all k ≥ 0.

Problem 1-2. Prove that for each integer n > 1, the expression

\underbrace{\sqrt{1 + \sqrt{1 + \sqrt{1 + ⋯}}}}_{n 1’s}

is irrational. For example, for n = 2 this is \sqrt{1 + \sqrt{1}}. You may assume that \sqrt{2} is irrational.

Problem 1-3. Define the binomial coefficient \binom{n}{k} = \frac{n!}{k! (n − k)!} for 0 ≤ k ≤ n. This is

read “n choose k,” and is the number of ways of choosing k distinct objects from a set of n distinct objects. (Although you can’t use this fact in your proofs unless you prove it first.) Don’t forget that 0! is defined to be 1. The binomial coefficient is defined to be 0 if k < 0 or k > n. Show that

(a) \binom{n}{k} = \binom{n − 1}{k}+\binom{n − 1}{k − 1} for any integers n and k such that 0 ≤ k ≤ n,

and

(b)  ∑_{k=0}^{n} \binom{k}{m} = \binom{n + 1}{m + 1} for any nonnegative integers n and m.

Problem 1-4. Let θ be an angle for which sin θ and cos θ are rational. Prove that for all integers n, sin nθ and cos nθ are rational.

Problem 1-5. Show that 5 divides 3^{2k} + 4^{k+1} for all integers k ≥ 0.