MAT 118 Spring 2013

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.

A proof by matematical induction involves two steps

- Show that the statement holds for the smallest number mentioned.
- Show that if it holds for a number $k$, then it holds for the next number, $k+1$. (This usually involves a calculation).

- 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$.
- 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$.

$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,