## MAT118 Review for Midterm III

### Material from Week 7

Understand how to use mathematical induction to prove a statement
about an arbitrary number $n$ (see notes
with homework 7). Be able to prove that the sum of the first $n$
numbers (i.e. $1+2+3+\cdots +n$) is equal to $\frac{1}{2}n(n+1)$.
Be able to prove that the sum of the first $n$
*odd* numbers (i.e. $1+3+5+\cdots +(2n-1)$)
is equal to $n^2$.

Know how to construct the Fibonacci numbers (p. 55). Understand
the "converging quotients" discussion on pp. 56, 57, 58 and why
the limit of the fractions defined by adjacent Fibonacci
numbers (the $(n+1)$st over the $n$th) is equal to $\frac{1}{2}
(1+\sqrt{5})$.
Most facts about the Fibonacci numbers need to be proved using
induction (since the numbers themselves are defined inductively).
See Mindscapes 7 and 8 on pp. 62, 63.

### Material from Week 8

Be able to convert numbers from base-$10$ to base-$2$
and back (see notes).
Be able to perform long division with base-$10$ and base-$2$
numbers, in order to implement the division algorithm (p. 69).
Understand why the remainder is always strictly less than the divisor.

### Material from Week 9

Understand the definition of "prime number" (remember, $1$
is not considered a prime). Understand why if a number $n$
has no factor $>1$ and less than or equal to $\sqrt{n}$,
then $n$ must be a prime. Be able to determine whether a number
less than $250$ is prime or not. Be able to prove that there
are infinitely many prime numbers (pp.72-74).

Understand how the $UPC$ code works. Be able to
reconstruct any single missing digit in a $UPC$ code.
Understand modular arithmetic, like the calculations on p. 89.
### Material from Week 10

In modular arithmetic with a *prime* modulus $p$, be
able to solve equations of the form $ax=b$ *mod* $p$.
(See notes).

*April 20, 2013*