Due:    Nov 17, 2023 @ 11:59 PM

Instructions:

. HW instructions

. academic integrity and collaboration

Problem 1 [12 pts]:  Spot the induction error:  All Horse Are Same Color

The following ”Theorem”  and inductive proof incorrect ”show” that  all horses have the same color.  (Of course, this statement is false).  Identify the error in reasoning below by offering clear, compelling and concicse reasoning.

“Reminder” P(n):

Let P (n) is the proposition that all the horses in a set of n horses are the same color.

Basis Step P(1):

Clearly, P (1) is true: if a group of horses contains only 1 horse then they all have the same color.

Inductive Step P(n) → P(n + 1):

Assume that P (n) is true, so that all the horses in any set of n horses are the same color.  Consider any n + 1 horses; number these as horses 1, 2, 3, .  .  .  , n, n +  1.  Now the first n of these horses all must have the same color, and the last n of these must also have the same color.  Because the set of the first n horses and the set of the last n horses overlap, all n + 1 must be the same color. Therefore P(n) → P(n + 1).

Problem 2 [22 pts]:  Upper triangular matrix

The diagonal of a square matrix refers to all elements in a line from the top-left to the bottom- right of the matrix.   For  example, in the 3 × 3  matrix below,  all diagonal entries are  1 where off-diagonal entries are 0:

Note that the only entry in a 1 × 1 matrix is on the diagonal.

The upper-diagonal of a matrix are all entries which are on the diagonal or above.  For example, in the 3 × 3 matrix below, all upper-diagonal entries are 1 where non-upper-diagonal entries are 0: