SOAR Homework Five

These homework problems are meant to expand your understanding of what goes on during class. Any you turn in will be graded and returned to you. Answers may or may not be posted on the web, depending on demand.

Problems

1. These problems involve mathematical induction. That is, see if you can prove these using induction, as done in class.
   1. Show that Sum_k=1ⁿ (2k-1) = n².

   2. Show that Sum_k=1ⁿ k² = [(n(n+1)(2n+1))/6].

   3. Show that Sum_k=1ⁿ k³ = ( [(n(n+1))/2] )².

   4. Let F(n) be the nth Fibonacci number. That is, F(1) = 1, F(2) = 1, and F(n) = F(n-1)+F(n-2) for n ³ 3. Show that Sum_k=1ⁿ F(k)² = F(n)F(n+1).

   5. Show that 2²ⁿ+3²ⁿ+5²ⁿ is divisible by 19 for every n ³ 1. (Hint: prove that if this is true for n then it is also true for n+2. You will need two base cases here - one for odd n and the other for even n.)

2. I claimed today that the fifth Fermat number, F₅ = 2²⁵+1, is not prime. Factor this number. (This was done by Euler in 1732. You may use resources that Euler did not have available, such as electricity. Please don't simply use the web, though; try to factor this yourself.)

3. On Friday at 3:00 PM, I will publish on the web page a public key and an encrypted message. I will encrypt the message using A=01, B=02, up through Z=26 and space as 27 and concatenate a fixed number of characters at a time. I will not use lower-case letters or punctuation.
   1. Decrypt the message using my public key.

   2. Factor my product of two primes and send me a message encrypted using my key.

   3. Make up your own public and private key and email me a message with these keys. I will post the message and the public key on the web page. (I may restrict the size of the primes permitted.) Your key and message are due by the start of class next week.

   4. Next week, decrypt everyone else's messages.

   5. If possible, ``break'' other people's code and email me a message using their private key. (Also send me a factorization of their product of two primes.)

   This is something of a race. Prizes may or may not be awarded.

A Puzzle

This problem was given to me by another post-doctoral fellow. He's interested in knowing the general answer (part (d)).

Consider the rearrangements of the numbers from 1 to n. For example, consider { 1 3 2} (so here n=3). There is one ``decrease'' in that: from 1 to 3 is an increase, but 3 to 2 is a decrease. To each re-arrangement, we assign +1 if there are an even number of decreases, and -1 if there are an odd number. So our example {1 3 2} would be assigned -1.

Now let S(n) be the sum of these values of +1 and -1 over all n! possible re-arrangments of {1 2 3  ...  n}. We'll compute S(3): the 3!=6 re-arrangements are:

Summing these six numbers, we get S(3) = +1-1-1-1-1+1 = -2.

1. Compute S(2).
2. Compute S(4).
3. Compute S(n) for n even. (Hint: can you group the re-arrangements in a way that makes the sum simple?)
4. Compute S(n) for n odd. (This is what my friend would like an answer for. He and I currently don't know a general form for S(n). We do know the answer to part (c), though.)

These problems are also available as a pdf file.

Solutions

Please email Peter if you are interested in answers or solutions for the web. Thanks.