Description
Problem 1. (25 points)
Use induction on n to prove that
nX−1
i=0
i
2
i
= 2 −
n + 1
2
n−1
Solution.
1
nX−1
i=0
i
2
i
= 2 −
n + 1
2
n−1
is true for all n ≥ 1
Basis Step: Show P(1)
P(1) = 2 −
1 + 1
2
1−1
= 2 −
2
1
= 0
P(1) = X
1−1
i=0
i
2
i
=
0
2
0
= 0
∴ P(0) holds
Inductive Step: Show P(k) → P(k + 1)
Assume P(k)for arbitrary k > 1 :
k
X−1
i=0
i
2
i
= 2 −
k + 1
2
k−1
Show P(k + 1) :X
k
i=0
i
2
i
= 2 −
k + 2
2
k
X
k
i=0
i
2
i
=
k
2
k
+
k
X−1
i=0
i
2
i
=
k
2
k
+ 2 −
k + 1
2
k−1
By HI
= 2 −
k + 2
2
k
∴ P(k) → P(k + 1) holds
∴
nX−1
i=0
i
2
i
= 2 −
n + 1
2
n−1
holds for all n ≥ 1 by mathematical induction
2
Problem 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.
Solution.
Base Step: if two people A and B are at a paty, you ask if they know one another. If one of the two peole
says Yes, and the other one says No, then the person who said No is a celebrity, else there is not a celebrity
present
Inductive Step: Assume that the above statement is true for a party of k people and prove that it is also
true for a party of k + 1 people.
Let A and B be party members. Ask A if they know B. If they answer Yes, A is not a celebrity. Else, if
they answer no then it follows that B is not a celebrity. One party member has now been ruled out as being
a celebrity. Going on to the next n party members, use the inductive hypothesis to find the celebrity with
3(n − 1) questions.
If there is a celebrity C, ask C if they know the last person. Also ask the last person if they know C. If C
does not know the last party member and the last party member knows C, then C is a celebrity.
1
If there were two, they would know each other. A particular party may have no celebrity
3
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.
Solution.
P(n) =
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist: Did you…
1. abide by the Aggie Honor Code?
2. solve all problems?
3. start a new page for each problem?
4. show your work clearly?
5. type your solution?
6. submit a PDF to eCampus?
4
Powered by TCPDF (www.tcpdf.org)
