Due:    Midnight, Friday, September 28.

Section 3.6:  Problems: 2, 4, 20, 23c-d, 38.
Section 3.7:  Problems 4, 6, 12, 27, 46.
Section 4.1:  Problems 6, 7, 11, 16, 18, 32, 47, 49.

1. Prove by induction that for n>4, 2ⁿ>n².
2. Take any integer n, and partition it in two parts each greater than zero.  For example 16 might be partitioned into 3 and 13.  Calculate the product of the two numbers, in this case 39.  Repeat this process with each of the two numbers, until you are down to 1, keeping track of the sum of all the products.  For example, if you start with 7, then you could get 3 and 4.  Three becomes 1 and 2.  Four becomes 2 and 2.  The two's all become 1 and 1.  This gives:  12 + 2 + 4 + 1 + 1 + 1 = 21.  Make a conjecture about the relationship of this sum to n.  Prove your conjecture by induction.
   
3. Prove that the square root of 3 is irrational using Aristotle’s techniques. Make sure to prove the appropriate lemma.
4. Compute by hand, the smallest positive integers x, y, u, v such that ax-by = bu-av = gcd(a,b) for each pair a, b below. Use the Euclidean algorithm and back tracking.  a. 99, 101  b. 36, 42
5. Prime Numbers:  How many distinct divisors are there for p^a, where p is a prime? How many distinct divisors are there for an arbitrary number m?   Hint: Factor m  into its prime factors so that m = p₁^a1p₂^a2…p_n^an.  Prove your answer by induction on n, the number of distinct prime factors.
   
6. RSA encryption. Let p=13 and q=11.Calculate an appropriate public code, and private code for doing RSA encrypting.   Assuming that each character in a message is represented by its ASCII value (an assigned table of integers from 0 to 127, can be found in many texts), encode the message “Too much work!”.
7. Guess the number of different ways for n people to arrange themselves in a straight line, and prove your guess is correct by induction.
8. Euclid proved that there are an infinite number of primes, by assuming that n is the highest prime, and exhibiting a number that he proved must either be prime itself, or else have a prime factor greater than n. Find the smallest n for which Euclid’s proof does not provide an actual prime number. (You can write a program to find it if you like).
9. In Stonehill-ball, you can score 11 points for a goal, and 7 for a near miss. Prove by induction that you can achieve any score greater than 60.
10. Guess a formula for the sum below, and prove you are right by induction.

1 + 1(2) + 2(3) + 3(4) + … + n(n+1)

shai@stonehill.edu

http://www.stonehill.edu/compsci/shai.htm