Think about all six problems, and come up with some ideas about how to solve them.
Then choose one or two of the problems and write up a careful solution.
Let q be a real number other than 1.Use induction on n to prove that:
q0 + q1 + q2 + ... + qn-1
= ( qn -1 )/ ( q -1)
Suppose f is a real function which satisfies
f(xy) = xf(y)+ yf(x) , for all real numbers x,y. Prove that f(1)=0 and that
f(un) = n un-1 f(u) for any positive integer n and any real u.
Use induction to prove that a set of n elements has 2n subsets.
In the village of Perfect Reasoning, each employer has an apprentice. At least
one apprentice is a thief. To remedy this without embarrassment, the mayor proclaims the
following true statements: "At least one apprentice in this town is a thief. Every thief
is known to be a thief by everyone except his or her employer, and all employers reason perfectly.
If n days from now you have concluded that your apprentice is a thief, you will come to
the village square at noon that day to denounce your apprentice." The villagers gather at noon every day
thereafter. If in fact k>0 of the apprentices are thieves, when will they be denounced, and how do
their employers reason?
(Hint: Study small values of k, and use induction to prove the pattern for all k.)
The Checkerboard Problem. Counting squares of sizes one-by-one through eight-
by-eight, an ordinary eight-by-eight checkerboard has 204 squares. How can we obtain a formula
for the number of squares of all sizes on an n-by-n checkerboard?
You have 12 coins, one of which is counterfeit. You don't know whether the counterfeit
coin is heavier or lighter that the others. Use three weighings on a balance with two pans to
find the counterfeit coin.
(Hint: Try to solve the same problem with 8 coins instead of 12.)