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 degree for all n Greaterthanorequalto 3. 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 degree for all n Greaterthanorequalto 3. The computer Science club is sponsoring a jigsaw puzzle contest. Jigsaw puzzles are assembled by fitting 2 pieces together to form a small block, adding a single piece to a block to form a bigger block, or fitting 2 blocks together. Each of these moves is considered a step in the solution. Use the second principle of induction to prove that the number of steps required to assemble an n-piece jigsaw puzzle is n - 1. OurWay Pizza makes only two kinds of pizza, pepperoni and vegetarian. Any pizza of either kind comes with an even number of breadsticks (not necessarily the same even number for both kinds). Any order of 2 or more pizzas must include at least 1 of each kind. When the delivery driver goes to deliver an order, he or she puts the completed order together by combining 2 suborders-picking up all the pepperoni pizzas from 1 window and all the vegetarian pizzas from another windows. Prove that for delivery of n pizzas, n Greaterthanorequalto 1, there are an even number of breadsticks included. Consider propositional wffs that contain only the connectives Wedge, Vee, and rightarrow (no negation) and where wffs must be parenthesized when joined by a logical connection. Count each statement letter, connection, or parenthesis as one symbol. For example, ((A) Wedge (B)) Vee ((C) Wedge (D)) is such a wffs, with 19 symbols. Prove that any such wff has an odd number of symbols. In any group of k people, k Greaterthanorequalto 1, each person is to shake hands with every other person. Find a formula for the number of handshakes, and prove that formula using induction.
Answer
73.
Applying the second principleof induction:
Base Step: Think of a puzzle with only 1 piece. This type of puzzle is already solved, so moves required is 0. As, n-1 =0, that is, 1-1 = 0, the base step is established.
Inductive Step: we need to prove that if the given statement is true for n<=k, then it is also true when n = k+1.
Think of the last move that will solve a puzzle with k+1 pieces. Let the blocks joined during this last move be A and B, which have a and b pieces, respectively. Note that a+b = k+1 and a,b <= k.As per the hypothesis, block A can be put together in a-1 steps and block B can be put together in b-1 steps. That means, the entire puzzle can be put together in (a-1) + (b-1) + 1 = a+b-1 = k steps, and this is what is needed to show.
Therefore, bby second principle of induction, we need n-1 steps to solve a jigsaw puzzle having n pieces.
-----------------------------------------------------------------------------------------------------------------Hence Proved.
76
The required formula is: f(k) = k(k - 1)/2.
Base step: when there is one person, i.e. k = 1 there is no handshake, and therefore, f(1) = 1(1 - 1)/2 = 0.
Inductive step: Our assumption is that, for a group of k 1, there are f(k) = k(k - 1)/2 handshakes.
Take a room full of k people. Suppose one more person has entered the room. Now, that person adds an extra k handshakes, so the number of handshakes becomes
f(k+1) = k(k - 1)/2 + k
= k(k + 1)/2 ----------------------------------------------------------------------------------------------Hence Proved
Homework Sourse
