PS07: More Induction

Due Fri 10/3 Mon 10/6 @ 10am.

Do these problems from the book, listed on pages 527 and 528.

  1. 5.37
  2. 5.39 (There's an error in this problem: the exponent on the matrix should be $n-1$, not $n$.) (Also, note that matrix exponentiation is defined just like exponentiation for numbers: it's repeated multiplication of the same thing by itself. A matrix raised to the zero power is just the identity matrix. Multiplying by the identity matrix gives you back whatever you started with.)
  3. 5.50
  4. 5.51

Also do these problems, listed on page 539.

  1. 5.54
  2. 5.59
  3. 5.65 (Note that a “bitstring” is a string, or sequence, of bits. So both 100110 and 10011001 are bitstrings, and the latter is a palindromic bitstring.)
  4. 5.66

Also do this problem.

  1. My house is just a few blocks away from a cool bar/restaurant/bowling alley/theater in Minneapolis. The part of Minneapolis where I live is laid out like a grid. For the sake of argument, let's imagine my house as the origin, and the bar $x$ blocks east and $y$ blocks north, at the corner $(x,y)$. We're only going to consider situations where the bar is north or east of me; that is, $x, y \ge 0$.

    So let's say I want to walk to the bar, following the street grid. I only ever walk north or east, one block at a time. Even under this constraint, I still have lots of choices: I could walk north until I'm even with the bar (at $(0,y)$) and then walk east, or I could walk east to $(x,0)$ and then north, or I could kinda zig-zag up and over. In all, there are

    $$\frac{(x+y)!}{x!y!}$$

    different choices of unique paths from my house to the bar. (We'll learn how to come up with this formula later in the course; for now, you'll have to take my word for it.) Try this formula out on a few small examples and convince yourself that it's correct. (Keep in mind that $0! = 1$.)

    Then, for your solution to this problem, prove that the above formula for the number of paths is correct for all $x,y \ge 0$. (Hint: think about a recursive definition of a path from my house to the point $(x,y)$. Pay careful attention to the cases where one coordinate is 0 but not the other!)