Prove that Algorithm 1 for computing n! when n is a nonnegative integer is correct.
The required algorithm is proved by induction.
The algorithm is for when n is non-negative, the base case is .
factorial (0) = 0!
By induction hypothesis,
Therefore, the required algorithm is proved by induction.
Let P(n) be the statement that for the positive integer .
a) What is the statement P(1)?
b) Show that P(1) is true, completing the basis step of
c) What is the inductive hypothesis?
d) What do you need to prove in the inductive step?
e) Complete the inductive step, identifying where you
use the inductive hypothesis.
f) Explain why these steps show that this formula is true whenever is a positive integer.
Prove that the first player has a winning strategy for the game of Chomp, introduced in Example 12 in Section 1.8, if the initial board is square. [Hint: Use strong induction to show that this strategy works. For the first move, the first player chomps all cookies except those in the left and top edges. On subsequent moves, after the second player has chomped cookies on either the top or left edge, the first player chomps cookies in the same relative positions in the left or top edge, respectively.]
Suppose that is a simple polygon with vertices listed so that consecutive vertices are connected by an edge, and and are connected by an edge. A vertex is called an ear if the line segment connecting the two vertices adjacent tolocalid="1668577988053" is an interior diagonal of the simple polygon. Two ears and are called nonoverlapping if the interiors of the triangles with vertices and its two adjacent vertices and and its two adjacent vertices do not intersect. Prove that every simple polygon with at least four vertices has at least two nonoverlapping ears.
94% of StudySmarter users get better grades.Sign up for free