Assignment:
All problems need to be proved using induction in proofs.
Q1. Consider n infinitely long straight lines, none of which are parallel and no three of which have a common point of intersection. Show that for n ≥ 1, the lines divide the plane into (n^2 + n + 2)/2 separate regions.
Q2. A string of 0s and 1s is to be processed and converted to an even-parity string by adding a parity bit to the end of the string. The parity bit is initially 0. When a 0 character is processed, the parity bit remains unchanged. When a 1 character is processed, the parity bit is switched from 0 to 1 or from 1 to 0. Prove that the number of 1s in the final string, that is, including the parity bit, is always even.
Q3. A simple closed polygon consists of n points in the plane joined in pairs by n line segments; each point is the endpoint of exactly two line segments.
a) Use the first principle of induction to prove that the sum of the interior angles of an n-sided simple closed polygon is (n-2)180° for all n ≥ 3.
b) Use the second principle of induction to prove that the sum of the interior angles of an n-sided simple closed polygon is (n-2) 180° for all n ≥ 3.
Q4. In any group of k people, k ≥ 1, each person is to shake hands with every other person. Find a formula for the number of handshakes, and prove the formula using induction.
Q5. Prove that any amount of postage greater than or equal to 12 cents can be built using only 4-cent and 5-cent stamps.
Provide complete and step by step solution for the question and show calculations and use formulas.