Assignment #2

Due Monday, April 19.

Note: In this assignment, use induction (either version) whenever you think that's the best method of proof. But also be alert for opportunities to use direct proofs that avoid induction.

Problems from these pages do not have to be done unless assigned.

To do but not hand in:

p. 27, Ex. 6;

p. 29, Ex. 5;

p. 35, Ex. 15;

C-1, C-2, C-4, C-6, C-8 below.

To hand in:

p. 27, Ex. 11;

p. 35, Ex. 10;

C-3, C-7, C-9, C-10, C-12, C-13 below;

Problem C-1. Recall that Stirling's approximate formula for $n!$ is

$$n! \sim S _ n = {\frac{\displaystyle n ^ n}{\displaystyle e ^ n}} \sqrt{2 \pi n},$$

meaning that $s _ n / n! \rightarrow 1$ as $n \rightarrow \infty$. (For example, 10! = 3,628,800, $s _ {10}$ = 3,598,695.6..., and $s _ {10} / 10! = .9917\ldots$, so that at $n = 10$ the approximation is already valid to within $1\%$.)

Using Stirling's approximation, find an approximation for $\binom{2n}n$.

Problem C-2. (a) Write out Pascal's Triangle through row 7.

(b) Notice that for each prime $p$, all the coefficients in row $p$ are divisible by $p$, except for the 1's at the ends. In other words, $p \vert \binom pk$ for $0 < k < p$. Prove that this is true for all primes $p$. (Useful principle for primes: $p \vert ab \Rightarrow p \vert a$$\mbox { or } p \vert b$. Or think in terms of prime factorizations.)

Problem C-3. (a) Develop and prove a simple formula for

$$\binom n0 + 2 \binom n1 + 2^2 \binom n2 + \dots + 2^n \binom nn.$$

(b) Develop and prove a simple formula for

$$\binom n0 - 2 \binom n1 + 2^2 \binom n 2 - \dots + (-1)^n 2^n \binom n n.$$

Problem C-4. In the ASCII computer code for characters, which is understood by essentially all computers, printers, etc., the upper-case letters A, B, C,...have codes 65, 66, 67, etc. (in the decimal version) and the lower-case letters have decimal codes 97, 98, 99, etc. Explain how these codes make more sense in binary (which is what the computer actually uses).

Problem C-5. (a) Describe $2^n - 1$ in binary.

(b) Describe $2^n - 1$ in hexadecimal if $n$ is divisible by 4.

Problem C-6. (a) What is $2^{100}$, approximately, as a power of 10?

(b) If you buy a computer whose hard disk has 80 gigabytes, which we can think of as numbered locations, how many bits (binary digits) does it take to express the location numbers? How many hexadecimal digits? (One byte is 8 bits, but that doesn't matter here since it's the bytes that are numbered.)

Problem C-7. (a) Find the square of $91827364 _ {10}$ by using a hand calculator and ``superdigits'' base $10^4$. Your work will have the pattern shown. (This has more lines than the multiplication algorithm we learned in elementary school, in which some lines are combined by carrying. Here carrying occurs only in the final addition.)

			D	D
		$\times$	D	D
			D	D
		D	D
		D	D
	D	D
	D	D	D	D

(b) In binary, do a long division of $1011$ into $110010$ (getting a quotient and remainder). Check by using decimal.

Problem C-8. Which positive integer less than 1000 has the most divisors? (Reasoning?)

Problem C-9. There is a row of 100 empty lockers, all shut. A student comes by and opens every locker. Another student comes by and closes lockers 2, 4, 6, and so on. Another student comes by and changes lockers 3, 6, 9, and so on, opening closed ones and closing open ones. Another student comes by and changes lockers 4, 8, 12, and so on. This process continues up to 100 students. At the end, which lockers are open, and why?

Problem C-10. Find $\gcd(99179,99999)$ two ways: (a) By the Euclidean algorithm; (b) by factoring. (For the Euclidean algorithm, you can use a calculator; for factoring, you may use the calculator on the class web page.)

Problem C-11. Find two integers among 1 to 100 such that the Euclidean algorithm takes as many steps as possible. (Give your reasoning.)

Problem C-12. The Fibonacci sequence is $0, 1, 1, 2, 3, 5, 8, 13, \dots$, where each term is the sum of the preceding two. In other words, if we call these terms $F _ 0, F _ 1, F _ 2, \dots$, the sequence is defined by $F _ 0 = 0$, $F _ 1 = 1$, and recursively $F _ n = F _ {n-2} + F _ {n-1}$ for $n \geq 2$.

(a) Show that every two consecutive terms of the Fibonacci sequence are relatively prime (i.e., have gcd = 1).

(b) Develop and prove a simple formula for the value of $F _ {n-1} F _ {n + 1} - F _ n ^ 2$. (Combine the cases of $n$ even and $n$ odd if you can.)

(c) How does Bezout's Theorem work for consecutive terms of the Fibonacci sequence? (Can you say explicitly what the coefficients $x$ and $y$ are?)

(d) Prove that $\left[\begin{array}{cc}F _ {n-1}& F _ n\ F _ n& F _ {n+1}\end{array}\right] = \left[\begin{array}{cc}0&1\ 1&1\end{array}\right] ^ n$. This is valid even for $n=0$ if we let $F _ {-1} = 1$ (which fits the recursive definition for the Fibonacci sequence).

(e) Does (c) help with solutions for any other part of the problem?

Problem C-13. (a) The golden mean or golden ratio is the positive number $\rho$ such that $\rho^2 = \rho + 1$. Find $\rho$ explicitly using the quadratic formula.

(b) Verify that the other solution of $x^2 = x + 1$ is $\bar \rho = 1 - \rho = - \frac 1 \rho$. (Note: $\rho \approx 1.618\dots$ and so $\bar \rho \approx -0.618\dots$.)

(c) Show that the sequence $1, \rho, \rho^2, \dots$ follows the same recursion as the Fibonacci sequence. What about $1, \bar \rho, \bar \rho^2,\dots$?

(d) A direct formula for Fibonacci: Show that $F _ n = {\frac{\displaystyle \rho ^n - \bar \rho ^ n}{\displaystyle \sqrt 5}}$.

(Note: Since $\vert\bar \rho\vert < 1$, as $n$ gets large the term involving $\bar \rho$ becomes negligible. In fact, even for small $n$, $F _ n$ can be obtained by rounding ${\frac{\displaystyle \rho^n}{\displaystyle \sqrt 5}}$ to the nearest integer. For example, ${\frac{\displaystyle \rho^{10}}{\displaystyle \sqrt 5}} = 55.0036$ and $F _ {10} = 55$.)

Problem C-14. In computer graphics, a Bézier¹curve is a parametric curve with polynomial coefficient functions, specified not by giving the polynomial coefficients but rather by giving ``control points''. Binomial coefficients are needed in the construction.

(a) Starting from the class home page http://www.math.ucla.edu/~baker/117/ try the Bézier demo, following the directions for it. Move the control points around a lot to get a feel for the possibilities. Can you make a curve that loops around to cross itself?

(Note: These are cubic (degree 3) Bézier curves, which are the most common. As you see, we don't use the whole infinite curve but just a segment.)

Bézier curves are constructed as follows (for degree 3):

Step 1: Expand $(s + t)^3 = s^3 + 3 s^2 t + 3s t^2 + t^3$, as in the binomial theorem.

Step 2: Put these terms in a list instead of adding them: $s^3, 3 s^2 t, 3s t^2, t^3$.

Step 3: Put $s = 1-t$, to get cubic polynomials, which we can call $a(t) = (1-t)^3, b(t) = 3 (1-t)^2 t, c(t) = 3 (1-t) t^2, d(t) = t^3$.

Step 4: If the four control points are $A, B, C, D$, the curve is $P(t) = a(t) A + b(t) B + c(t) C + d(t) D$, for $0 \leq t \leq 1$, where we treat points like vectors.

Here recall that a parametric plane curve can be thought of as a moving point $P(t) = (x(t), y(t))$, where $t$ is time. For example, if the control points are
$A = (3,2), B = (7,1), C = (2,4), D = (-1, 3)$ then
$P(t) = a(t)(3,2) + b(t) (7,1) + c(t) (2,4) + d(t) (-1,3)$,
or looking at coordinates separately,
$x(t) = 3a(t) + 7b(t) + 2c(t) -d(t)$ and
$y(t) = 2a(t) + b(t) + 4c(t) + 3d(t)$.

(b) For control points $A, B, C, D$, what are $P(0)$ and $P(1)$?

(c) Show that the coefficients add to 1 at all times. (So we're really taking a ``weighted average'' of the four control points, with total weight 1. The weights change with time, and that makes the point move to trace out the curve.)