91Ó°ÊÓ

Prove that the program segment $$ \begin{array}{l}{y :=1} \\ {z :=x+y}\end{array} $$ is correct with respect to the initial assertion \(x=0\) and the final assertion \(z=1\)

Verify that the program segment $$ \begin{array}{c}{x :=2} \\ {z :=x+y} \\ {\text { if } y>0 \text { then }} \\\ {z :=z+1} \\ {\text { else }} \\ {z :=0}\end{array} $$ is correct with respect to the initial assertion \(y=3\) and the final assertion \(z=6\)

Determine whether each of these proposed definitions is a valid recursive definition of a function \(f\) from the set of nonnegative integers to the set of integers. If \(f\) is well defined, find a formula for \(f(n)\) when \(n\) is a nonnegative integer and prove that your formula is valid. a) \(f(0)=0, f(n)=2 f(n-2)\) for \(n \geq 1\) b) \(f(0)=1, f(n)=f(n-1)-1\) for \(n \geq 1\) c) \(f(0)=2, f(1)=3, f(n)=f(n-1)-1\) for \(n \geq 2\) d) \(f(0)=1, f(1)=2, f(n)=2 f(n-2)\) for \(n \geq 2\) e) \(f(0)=1, f(n)=3 f(n-1)\) if \(n\) is odd and \(n \geq 1\) and \(\quad f(n)=9 f(n-2)\) if \(n\) is even and \(n \geq 2\)

Use strong induction to show that every positive integer can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers \(2^{0}=1,2^{1}=2,2^{2}=4\) and so on. [Hint: For the inductive step, separately con- sider the case where \(k+1\) is even and where it is odd. When it is even, note that \((k+1) / 2\) is an integer. \(]\)

Describe a recursive algorithm for multiplying two non- negative integers \(x\) and \(y\) based on the fact that \(x y=2(x \text { . }\) \((y / 2) )\) when \(y\) is even and \(x y=2(x \cdot\lfloor y / 2\rfloor)+x\) when \(y\) is odd, together with the initial condition \(x y=0\) when \(y=0\)

Use mathematical induction to prove the inequalities in Exercises \(18-30 .\) Let \(P(n)\) be the statement that \(n !

Pick's theorem says that the area of a simple polygon \(P\) in the plane with vertices that are all lattice points (that is, points with integer coordinates) equals \(I(P)+B(P) / 2-1\) where \(I(P)\) and \(B(P)\) are the number of lattice points in the interior of \(P\) and on the boundary of \(P,\) respectively. Use strong induction on the number of vertices of \(P\) to prove Pick's theorem. [Hint: For the basis step, first prove the theorem for rectangles, then for right triangles, and finally for all triangles by noting that the area of a tri- angle is the area of a larger rectangle containing it with the areas of at most three triangles subtracted. For the inductive step, take advantage of Lemma \(1 . ]\)

Suppose that \(P\) is a simple polygon with vertices \(v_{1}, v_{2}, \ldots, v_{n}\) listed so that consecutive vertices are con- nected by an edge, and \(v_{1}\) and \(v_{n}\) are connected by an edge. A vertex \(v_{i}\) is called an ear if the line segment connecting the two vertices adjacent to \(v_{i}\) is an interior diagonal of the simple polygon. Two ears \(v_{i}\) and \(v_{j}\) are called nonoverlapping if the interiors of the triangles with vertices \(v_{i}\) and its two adjacent vertices and \(v_{j}\) and its two adjacent vertices do not intersect. Prove that every simple polygon with at least four vertices has at least two nonoverlapping ears.

Give a recursive definition of a) the set of odd positive integers. b) the set of positive integer powers of 3 . c) the set of polynomials with integer coefficients.

Give a recursive definition of a) the set of even integers. b) the set of positive integers congruent to 2 modulo 3 . c) the set of positive integers not divisible by 5 .