## 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