## Stony Brook University MAT 118 Spring 2013

### Assignment 7 due in Recitation, week of March 25

Mathematical Induction is a way of establishing the truth of a statement about the natural numbers $1, 2, 3, 4, \dots$ .
By "statement about the natural numbers" we mean something like:
• The sum $1+3+5+\cdots+(2n-1)$ of the first $n$ odd numbers is equal to $n^2$.
• Every natural number can be written as a product of prime numbers. This product is unique up to an ordering of the factors. [This uses the concept of prime number: a natural number only divisible by itself and $1$. E.g. $2, 3, 5, 7, 11, 13, \dots$ . The number $1$ itself is not counted as a prime.]
• Every even number greater than $2$ can be written as the sum of two primes.
(The first statement we proved in class. The second is called "The Fundamental Theorem of Arithmetic" and is proved in Euclid. The third is called "The Goldbach Conjecture" and goes back to 1742. It has been checked for numbers up to $4\times 10^{18}$ but has still not been proved in general.)

A proof by matematical induction involves two steps

1. Show that the statement holds for the smallest number mentioned.
2. Show that if it holds for a number $k$, then it holds for the next number, $k+1$. (This usually involves a calculation).
Here is how we proved in class that the sum of the first $n$ odd numbers is equal to $n^2$.
1. We checked it for $n=1$:  $1 = 1^2$. That looked weird so we checked it for $n=2$:  $1+3 = 2^2$ and for $n=3$:  $1+3+5 = 3^2$.
2. We suppose it holds for some number $k$: $$1+3+\dots+(2k-1)=k^2.$$ (Remember that $1=2\times 1 - 1$ is the $1$st odd number, that $3 = 2\times 2 -1$ is the $2$nd one, that $5=2\times 3 -1$ is the $3$rd, ... , so $2\times k-1$ will be the $k$th).
The next odd number will be $2k+1$. We add it to both sides $$1+3+\dots+(2k-1)+(2k+1) =k^2+2k+1.$$ Now we observe that $(k+1)(k+1)= k^2+2k+1.$ So the right hand side of our equation is exactly $(k+1)^2$. We have established that if the statement holds for $k$, it holds for $k+1$.
This completes the proof.

### The Fibonacci numbers

(See page 55 and Mindscape 6 on pages 61-62). They are defined by

$F_1 = 1$,   $F_2 = 1$   and $F_{n+1} = F_n + F_{n-1}$ for $n\geq 2.$

A. Notice that $F_1 =1, F_2 = 1, F_3 = 2, F_4 =3, F_5 = 5, F_6 = 8.$ Show that $F_n$ is even exactly when $n$ is a multiple of $3$.

B. Notice that
$1^2 = 1\times 2 -1$, i.e. $F_2^2 = F_1F_3 -1$
$2^2 = 1\times 3 +1$, i.e. $F_3^2 = F_2F_4 +1$
$3^2 = 2\times 5 -1$, i.e. $F_4^2 = F_3F_5 -1$
$5^2 = 3\times 8 +1$, i.e. $F_5^2 = F_4F_6 +1$. Show that in general
$F_n^2 = F_{n-1}F_{n+1}-1$ if $n$ is even,
$F_n^2 = F_{n-1}F_{n+1}+1$ if $n$ is odd.
Hint: Work by induction. Suppose $n$ even and you know $F_n^2 = F_{n-1}F_{n+1}-1$. Write $F_{n+1}^2$ as $F_{n+1}(F_n + F_{n-1})$. Multiply out and use your induction hypothesis. Repeat for $n$ odd.

C. Fibonacci numbers in Pascal's Triangle. Write the triangle with vertical rows:

$1$
$1$ $1$
$1$ $2$  $1$
$1$ $3$  $3$   $1$
$1$ $4$  $6$   $4$   $1$
$1$ $5$ $10$ $10$  $5$   $1$
$1$ $6$ $15$ $20$ $15$  $6$  $1$
$1$ $7$ $21$ $35$ $35$ $21$ $7$ $1$

Now sum the numbers along the upward-slanting diagonals:
$1$
$1$
$1+1$
$1+2$
$1+3+1$
$1+4+3$
$1+5+6+1$, etc.
Show that the diagonal sums in Pascal's triangle are exactly the Fibonacci numbers. You will need to use both the inductive definition of the Fibonacci numbers and the inductive construction of Pascal's triangle.

D. Mindscape 10 on page 63,