## Description

Problem 1. (25 points)

Use induction on n to prove that

nX−1

i=0

i

2

i

= 2 −

n + 1

2

n−1Problem 2. (25 points)

A guest at a party is a celebrity if this person is known by every other guest, but knows none of them.

There is at most one celebrity at a party1

. Your task is to find the celebrity, if one exists, at a party by

asking only one type of question – asking a guest whether they know a second guest. Everyone must answer

your questions truthfully. That is, if Alice and Bob are two people at the party, you can ask Alice whether

she knows Bob; she must answer correctly. Use mathematical induction to show that if there are n people at

the party, then you can find the celebrity, if there is one, with 3(n−1) questions. Hint: First, ask a question

to eliminate one person as a celebrity. Then use the inductive hypothesis to identify a potential celebrity.

Finally, ask two more questions to determine whether that person is actually a celebrity.

Problem 3. (25 points)

Determine which Fibonacci numbers are divisible by 3. Use strong induction on n to prove your conjecture.

The Fibonacci sequence satisfies the recurrence relation fn = fn−1 + fn−2 where f0 = 0 and f1 = 1.

Problem 4. (25 points)

Restaurant 222 offers gift certificates in denominations of $8 and $15. Determine the possible total amounts

you can form using these denominations of gift certificates. Prove your answer using strong induction