CSCI 2405
Discrete Mathematics II
Fall 2017
Homework Assignment 5

Due: Friday, October 27, at the beginning of class.

Prove each of the following claims by mathematical induction on n. Write clear and readable proofs. There will be no credit for sloppy or unclear work.

Do forward proofs. Work from what you know to facts that you can conclude. Do not do backwards proofs, working from a goal that you want to prove to subgoals.

If you believe that a claim is false, make sure that you understand the claim. Ask about it if you still think it is false. Do not just turn in a paper saying that the claim is false.

For any two integers x and y, x is a factor of y if and only if there exists an integer k so that y = kx.

1. Claim. For all integers a and b and for every positive integer n, a − b is a factor of aⁿ − bⁿ.

   Hint. For n > 2, you know

   1. a − b is a factor of aⁿ⁻¹ − bⁿ⁻¹.
   2. a − b is a factor of aⁿ⁻² − bⁿ⁻².

   Convert facts 1 and 2 to equations by the definition of what it means for one number to be a factor of another. Multiply both sides of equation 1 by (a+b). Multiply both sides of equation 2 by ab. What can you conclude from those equations?

2. Claim. For every positive integer n, 43 is a factor of 6ⁿ⁺¹ + 7²ⁿ⁻¹.