91Ó°ÊÓ

A partition of a positive integer \(n\) is a way to write \(n\) as a sum of positive integers where the order of terms in the sum does not matter. For instance, \(7=3+2+1+1\) is a partition of \(7 .\) Let \(P_{m}\) equal the number of different partitions of \(m,\) and let \(P_{m, n}\) be the number of different ways to express \(m\) as the sum of positive integers not exceeding \(n\). a) Show that \(P_{m, m}=P_{m}\) . b) Show that the following recursive definition for \(P_{m, n}\) is correct: $$P_{m, n}=\left\\{\begin{array}{ll}{1} & {\text { if } m=1} \\ {1} & {\text { if } n=1} \\ {P_{m, m}} & {\text { if } m< n} \\ {1+P_{m, m-1}} & {\text { if } m=n>1} \\ {P_{m, n-1}+P_{m-n, n}} & {\text { if } m>n>1}\end{array}\right.$$ c) Find the number of partitions of 5 and of 6 using this recursive definition.

Exercises \(49-51\) present incorrect proofs using mathematical induction. You will need to identify an error in reasoning in each exercise. What is wrong with this "proof" that all horses are the same color? Let \(P(n)\) be the proposition that all the horses in a set of \(n\) horses are the same color. Basis Step: Clearly, \(P(1)\) is true. Inductive Step: Assume that \(P(k)\) is true, so that all the horses in any set of \(k\) horses are the same color. Consider any \(k+1\) horses; number these as horses \(1,2,3, \ldots, k, k+1 .\) Now the first \(k\) of these horses all must have the same color, and the last \(k\) of these must also have the same color. Because the set of the first \(k\) horses and the set of the last \(k\) horses overlap, all \(k+1\) must be the same color. This shows that \(P(k+1)\) is true and finishes the proof by induction.

Show that \(\left[\left(p_{1} \rightarrow p_{2}\right) \wedge\left(p_{2} \rightarrow p_{3}\right) \wedge \cdots \wedge\left(p_{n-1} \rightarrow p_{n}\right)\right]\) \(\quad \rightarrow\left[\left(p_{1} \wedge p_{2} \wedge \cdots \wedge p_{n-1}\right) \rightarrow p_{n}\right]\) is a tautology whenever \(p_{1}, p_{2}, \ldots, p_{n}\) are propositions, where \(n \geq 2\)

Show that \(n\) lines separate the plane into \(\left(n^{2}+n+2\right) / 2\) regions if no two of these are parallel and no three pass through a common point.

Let \(a_{1}, a_{2}, \ldots, a_{n}\) be positive real numbers. The arithmetic mean of these numbers is defined by $$ A=\left(a_{1}+a_{2}+\cdots+a_{n}\right) / n $$ and the geometric mean of these numbers is defined by $$ G=\left(a_{1} a_{2} \cdots a_{n}\right)^{1 / n} . $$ Use mathematical induction to prove that \(A \geq G\) .

A guest at a party is a celebrity if this person is known by every other guest, but knows none of them. There is at most one celebrity at a party, for if there were two, they would know each other. A particular party may have no celebrity. Your assignment is to find the celebrity, if one exists, at a party, by asking only one type of question asking a guest whether they know a second guest. Everyone must answer your questions truthfully. That is, if Alice and Bob are two people at the party, you can ask Alice whether she knows Bob; she must answer correctly. Use mathematical induction to show that if there are \(n\) people at the party, then you can find the celebrity, if there is one, with 3\((n-1)\) questions. [Hint: First ask a question to eliminate one person as a celebrity. Then use the inductive hypothesis to identify a potential celebrity. Finally, ask two more questions to determine whether that person is actually a celebrity. \(]\)

Suppose there are \(n\) people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information about all scandals each knows about. For example, on the first call, two people share information, so by the end of the call, each of these people knows about two scandals. The gossip problem asks for \(G(n),\) the minimum number of telephone calls that are needed for all \(n\) people to learn about all the scandals. Exercises \(69-71\) deal with the gossip problem. Find \(G(1), G(2), G(3),\) and \(G(4)\)

Suppose there are \(n\) people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information about all scandals each knows about. For example, on the first call, two people share information, so by the end of the call, each of these people knows about two scandals. The gossip problem asks for \(G(n),\) the minimum number of telephone calls that are needed for all \(n\) people to learn about all the scandals. Exercises \(69-71\) deal with the gossip problem. Use mathematical induction to prove that \(G(n) \leq 2 n-4\) for \(n \geq 4 .\) [Hint: In the inductive step, have a new person call a particular person at the start and at the end. \(]\)

Show that it is possible to arrange the numbers \(1,2, \ldots, n\) in a row so that the average of any two of these numbers never appears between them. [Hint: Show that it suffices to prove this fact when \(n\) is a power of \(2 .\) Then use mathematical induction to prove the result when \(n\) is a power of 2.]

Sometimes we cannot use mathematical induction to prove a result we believe to be true, but we can use mathematical induction to prove a stronger result. Because the inductive hypothesis of the stronger result provides more to work with, this process is called inductive loading. We use inductive loading in Exercise \(74-76\) . Suppose that we want to prove that $$ \sum_{j=1}^{n} j /(j+1) !<1 $$ for all positive integers \(n .\) a) Show that if we try to prove this inequality using mathematical induction, the basis step works, but the inductive step fails. b) Show that mathematical induction can be used to prove the stronger inequality $$ \sum_{j=1}^{n} j /(j+1) ! \leq 1-1 /(n+1) ! $$ for all positive integers \(n,\) implying that the weaker inequality is also true.