Homework (IV)

Problem 1

Use the principle of induction to prove that for all natural numbers $n$, \[ \displaystyle\frac{1}{1.2} + \frac{1}{2.3} + \ldots + \frac{1}{n .(n+1) } = \frac{n}{n+1} \]

Problem 2

1. Use the principle of induction to prove that $n$ people can line up in $n!$ different arrangements in a grocery store queue.
2. Use the result of the first part to conclude that the number of arrangements three people in a grocery store can line up is the same as the number of symmetries of an equilateral triangle.
3. Does the statement of the second part generalize to $n$ people and regular polygons with $n$-vertices.

Problem 3

Identify the mistake(s) in the following argument:

Claim. $ \displaystyle\sum_{k=0}^\infty k < \infty \, .$

Proof. We prove this claim by induction on variable $n$. Let $S_n$ be the finite sum $\displaystyle\sum_{k=0}^n k$ and consider the statement asserting that $S(n) < \infty$. The base case of induction holds since the claim is true for $n = 0$. Suppose the claim is true for $n$. Then it is true for $n + 1$, since the next sum is equal to the previous sum plus $n+1$, both of which are finite. By induction, $\displaystyle\sum_{k=0}^\infty k$ is finite and therefore, $\displaystyle\sum_{k=0}^\infty k < \infty$.

Problem 4

We are given $2n$ points in the 3-dimensional Euclidean space, and altogether $n^2 +1$ line segments are drawn between these points. Show that you can always find a triangle, that is there are at least three distinct points, any two of which are joined by a line segment.

Problem 5

Prove that if you divide the plane into regions using finitely many straight lines, then the regions can be colored with two colors in such a way that adjacent regions have opposite colors.

Problem 6

Show by induction that \[ \displaystyle\sum_{k=0}^n \binom {n+k} {k}\times \frac{1}{2^k} = 2^n \, .\]

Problem 7

In this problem you will prove the barber paradox in Lean. Suppose, in a village, there is a (male) barber that shaves all and only the men who do not shave themselves. This assumption yields the following contradiction:

By the assumption, the barber shaves himself if and only if he does not shave himself. Now, if the barber indeed shaves himself then this implies that he does not shave himself, a contradiction. So, the barber does not shave himself. If the barber does not shaves himself then by the assumption he does shave himself, again a contradiction.

Fill in the sorry’s below, to prove the barber paradox.

Tips & Hints

• For all problems (except problem 7) you have to write your proofs in clear English without much use of abbreviations. A good source to look up is the Chapter 4 of our textbook. In particular, you must explain which variant of the principle of induction you are using, the common (aka standard) one, or the strong one and in each case you must be explicit about the starting point and the base case. Make sure to state your assumptions and goals in your proof as clearly as possible, like “we want to prove blah blah blah”. Avoid excessive abbreviations and bad uses of the sign “$=$”. Remember that an informal pen-and-paper proof is different than a Lean proof.

• For problem 6, you need to know what the binomial coefficients are. They are explained in this section of the lesson on induction. You can also read a ton more about them in Wikipedia, but that is not necessary to solve problem 6. Again the Chapter 4 of our textbook is another excellent resource to learn more about binomial coefficients.

• In problem 2, a regular polygon is assumed to be convex.

• For problem 7, you might like to consult the Lean Cheat Sheet 📝 to refresh your memory about the Lean Labs on propositions 🧪 and predicates 🧪.