Problems

Find the error in the following proof that $2=1$. Consider the equation $a=b$. Multiply both sides by $a$ to obtain $a^{2}=a b$. Subtract $b^{2}$ from both sides to get $a^{2}-b^{2}=a b-b^{2}$. Now factor each side, $(a+b)(a-b)=b(a-b)$, and divide each side by $(a-b)$ to get $a+b=b$. Finally, let $a$ and $b$ equal 1, which shows that $2=1$.

Let $S(n)=1+2+\cdots +n$ be the sum of the first $n$ natural numbers and let $C(n)=1^{3}+2^{3}+\cdots +n^{3}$ be the sum of the first $n$ cubes. Prove the following equalities by induction on $n$, to arrive at the curious conclusion that $C(n)=S^{2}(n)$ for every $n$.

Find the error in the following proof that all horses are the same color. Claim: In any set of $h$ horses, all horses are the same color. Proof: By induction on $h$. Basis: For $h=1$. In any set containing just one horse, all horses clearly are the same color. Induction step: For $k \geq 1$, assume that the claim is true for $h=k$ and prove that it is true for $h=k+1$. Take any set $H$ of $k+1$ horses. We show that all the horses in this set are the same color. Remove one horse from this set to obtain the set $H_{1}$ with just $k$ horses. By the induction hypothesis, all the horses in $H_{1}$ are the same color. Now replace the removed horse and remove a different one to obtain the set $H_{2}$. By the same argument, all the horses in $H_{2}$ are the same color. Therefore, all the horses in $H$ must be the same color, and the proof is complete.

Show that every graph with two or more nodes contains two nodes that have equal degrees.

• ᴬ Ramsey's theorem. Let $G$ be a graph. A clique in $G$ is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with $n$ nodes contains either a clique or an anti-clique with at least $\frac{1}{2} \log_{2} n$ nodes.

ᴬ Use Theorem 0.25 to derive a formula for calculating the size of the monthly payment for a mortgage in terms of the principal $P$, the interest rate $I$, and the number of payments $t$. Assume that after $t$ payments have been made, the loan amount is reduced to 0. Use the formula to calculate the dollar amount of each monthly payment for a 30 -year mortgage with 360 monthly payments on an initial loan amount of $100,000 with a 5 annual interest rate.