3. To begin a proof by contradiction for “If n is even then n+1is odd,” what would you “assume true?

4. Prove that the following is not true byfinding a counterexample.

“The sum of any 3 consecutive integers iseven"

5. Show a Proof by exhaustion for thefollowing: For n = 2, 4, 6, n²-1 isodd

6.  Show an informalDirect Proof for “The sum of 2 evenintegers is even.”

Recursive Definitions

7.  The Fibonacci Sequenceis defined asfollows:                             

           F(1) = 1

           F(2) = 1

           F(n) = F(n-1) + F(n-2) for n>2.

     The first 10 numbers in the sequenceare 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

      Find F(13) = ______________ andF(14) =______________

8.  Prove the following property of the Fibonaccinumbers directly from thedefinition.                                                                                                        

           F(n+3) = 2F(n+1) + F(n-3)+ 2F(n-2)

9.  Find the 3^rd, 4^th and5^th values in the sequence.

           D(1) = 0

           D(n) = 2D(n-1) + 2 for n>1.

           D(2) = _______________________________________________

           D(3) = _______________________________________________

           D(4) = _______________________________________________

10.  Find the 3^rd, 4^th and5^th values in the sequence.

           D(1) = 1

           D(2) = 4

           D(n) = 2D(n-1) + D(n-2) for n>2.

           D(3) = _______________________________________________

D(4) = _______________________________________________

           D(5) = _______________________________________________

11.  Using the SelectionSort algorithm on p 169 inyour textbook, simulate the execution of the algorithm on thefollowing list L; write the list after everyexchange.  

L:    9, 2, 4, 8, 6

_______________

_______________

_______________

_______________