PS08: More Induction

Due Mon 4/20 @ 1:30pm.

The first set of problems below all relate to the Sierpinski Triangle. Here are some observations that might be helpful:

Do these problems from the book, listed on pages 516. Note that each proof needs only a weak hypothesis!

  1. 5.15 — Hint: define a value $\alpha$ that's equal to the area of the level-0 Triangle, and use it in all your computations. It makes your claim much easier to state, and the math in your proof much easier to follow.
  2. 5.16

Do these problems from the book, listed on pages 527 and 528. These ones will be easier if you use a strong hypothesis.

  1. 5.33
  2. 5.34
  3. 5.51

Also do these problems, listed on page 539.

  1. 5.59 (Note that this problem is only talking about non-negative even numbers.)
  2. 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.)
  3. 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$.

    Here are a few hints: