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
