Prove that each natural number \(n\geq 2\) can be uniquely written as a product of prime factors. More precisely, there are prime numbers \(p_1,\dots,p_s\) such that \(n = p_1\dots p_s\). Moreover, if \(n = q_1\dots q_l\) where \(q_1,\dots,q_l\) are prime, then \(s=l\) and after reordering we have \(q_1 = p_1,\dots,q_s=p_s\). This is the fundamental theorem of arithmetic.
The AM-GM inequality asserts that the arithmetic mean of nonnegative numbers is always at least their geometric mean. That is, if \(a_1,\dots,a_n\geq 0\), then \[\frac{a_1+\dots+a_n}{n}\geq \sqrt[n]{a_1\dots a_n}.\] Prove this inequality.
There are many proofs of this fact and quite a few of them are by induction. In fact, one of the most creative uses of induction can be found in Cauchy’s proof of the AM-GM inequality in Cours d’analyse.
Show that if \(1+3+5+7+...+97+99=50^2\), then \(1+3+5+7+...+97+99+101=51^2\). Don’t forget that \((a+b)^2=a^2+2ab+b^2\).
Prove that for all positive integers \(n\) there exists a partition of the set of positive integers \(k\le2^{n+1}\) into sets \(A\) and \(B\) such that \[\sum_{x\in A}x^i=\sum_{x\in B}x^i\] for all integers \(0\le i\le n\).
Let \(n\) be a positive integer. Show that \(3^{2n+4}-4^n\) is always divisible by \(5\).
Prove that \(n^{n+1}>(n+1)^n\) for integers \(n\ge3\).
Let \(n\) be a positive integer. Show that \(1+3+3^2+...+3^{n-1}+3^n=\frac{3^{n+1}-1}{2}\).
Show that all integers greater than or equal to \(8\) can be written as a sum of some \(3\)s and \(5\)s. e.g. \(11=3+3+5\). Note that there’s no way to write \(7\) in such a way.
Alice and Bob were playing outdoors. A mean lady told them that at least one of them has a muddy face and everyone who has a muddy face must step forward at the same time on the count of three. Then the mean lady will leave them alone.
If a child with clean face steps forward, he is punished. If nobody steps forward, then the mean lady will do the count again. The children are not allowed to signal to each other. How can Alice and Bob avoid punishment?
Alice, Bob and Claire were playing outdoors. A mean lady told them that at least one of them has a muddy face and everyone who has a muddy face must step forward at the same time on the count of three. Then the mean lady will leave them alone.
If a child with clean face steps forward, he is punished. If nobody steps forward, then the mean lady will do the count again. The children are not allowed to signal to each other. How can Alice, Bob and Claire avoid punishment?