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
- 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).
Here is how we proved in class that the sum of the first $n$
odd numbers is equal to $n^2$.
- 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$.
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,