1. A big product
Prove that, for all integers n greater than 1,
![\[\prod_{i=2}^{n} \left(1 - \frac{1}{i}\right) = \frac{1}{n}.\]](/pinewiki/CS202/2007/Assignments/HW03?action=AttachFile&do=get&target=latex_ac57f50d7acf86dcb2c709b6a1d369c780deef56_p1.png "\[\prod_{i=2}^{n} \left(1 - \frac{1}{i}\right) = \frac{1}{n}.\]")
2. A feudal tax system
Every day, a peasant earns 1 copper farthing. His landlord comes to him at the end of the day and taxes him for exactly 1/4 of his total wealth (including any money left over from previous days). Assuming that the two start with nothing and that neither person has any other source of income or expenditures, how much much does the landlord have after n days?
3. A counting game
Two small children are playing the game "I know a bigger number." The first player must name a natural number less than or equal to n, where n happens to be the largest number known to either child. Then the second player must name a larger number that is still less than or equal to n. The players continue to alternate with larger and larger numbers until one of them names n, at which point the game ends.
Given n, exactly how many different sequences of moves could the two children play?
4. Sets of functions
Given sets A and B, let AB be the set of all functions f:B→A.
Prove or disprove: |∅B| = 0 for any set B.
Prove or disprove: |1B| = 1 for any set B, where 1 = {∅}.
Prove or disprove: If A has at least two elements, then there exists an injection from B to AB.