Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Hints for the exercises on induction
Computer Laboratory > Course material > Discrete Mathematics > Hints for the exercises on induction

Please do try the questions by yourself before resorting to these hints!

  1. Standard induction.
  2. [n(n+1)/2]².
  3. 1 - 1/(n+1)!.
  4. 24n+6 + 32n+3 = 16.(24n+2 + 32n+1) - 7.32n+1,
    3n+2 + 42n+1 = 3.(3n+1 + 42n-1) + 13.42n-1,
    or use modular arithmetic.
  5. Induction (or solve directly as a second-order, homogeneous, linear difference equation).
  6. (1 + x)n+1 = (1 + x)(1 + x)n.
  7. Use induction with the hypothesis P(n) ≡ "A 2n×2n chessboard with one purple square can be covered with triominoes leaving the purple square exposed." The base case has n=0, and the inductive step involves four smaller problems in three of which you can choose where to put the purple square.
  8. The key to cell number n has been turned once for every factor of n, so the door will be left unlocked if n has an odd number of factors. The factors of n can be paired off unless n is a square.
  9. The only difficulty is understanding the notation. Just work through the details of n=2 and n=3 to understand it, before tackling the general case.
    The base case has n=0, so S=Ø.
    For the inductive step, let Pn be the product for S={1,2,...,n}. Pn+1=(1+xn+1)Pn. 1.Pn gives the subsets of Sn+1 that do not contain n+1 and xn+1Pn gives the subsets that do.
  10. By counting, the most extrovert guest shook 2n hands and the most timid shook none. The former shook hands with everyone apart from sibself and sis spouse. It follows that the maximal and minimal shakers were married to each other. Given that neither was the Master, the other could not have been the Master’s wife.
    Uninvite them. The answer is n.
  11. Ho, ho, ho...