Suppose \(n\) lines are drawn in the plane, dividing it into regions. Prove that these regions can be colored orange and blue in such a way that neighboring regions, ones sharing a line as a boundary, are different colors.
Solution
Proceeding inductively, when \(n=1\) you have two regions, so color one orange and the other blue and you’re good.
Next suppose you have a coloring for every collection of regions in the plane defined by \(k\) lines. Given \(k+1\) lines in the plane, chose one line \(\ell\) and remove it, and we’ll have an orange/blue coloring for what remains. Adding \(\ell\) back, we can update the coloring like this: on one side of \(\ell\) keep the coloring the same, and on the other side of \(\ell\) swap all the orange and blue. Now any regions neighboring along \(\ell\) must be different colors since they were the same region/color before the re-addition of \(\ell\), and any regions neighboring along a line besides \(\ell\) must be different colors from the coloring before the re-addition of \(\ell\).
Prove that for all positive integers \(n\), we have \(\displaystyle 1 + 2 + \dotsb + n = \frac{n(n+1)}{2}\,. \)
Solution
We’ll argue using mathematical induction. First notice that for \(n = 1\) the statement is true since \[1 = \frac{1(1+1)}{2}\,. \]
Now assume the statement is true for \(n = k\) for some specific positive integer \(k.\) I.e. we’re assuming that \(1 + 2 + \dotsb + k = \frac{k(k+1)}{2}\,.\) Our goal is to start from this fact and algebraically manipulate this equation to show that the statement is true for \(n = k+1\) too. I.e. that \(1 + 2 + \dotsb + (k+1) = \frac{(k+1)(k+2)}{2}\) too. Here’s how: \[ \begin{align*} 1 + 2 + \dotsb + k &= \frac{k(k+1)}{2} \\1 + 2 + \dotsb + k + \mathbf{(k+1)} &= \frac{k(k+1)}{2} + \mathbf{(k+1)} \end{align*} \] Then by cleaning up the right-hand side into a single expression: \[ \begin{align*} 1 + 2 + \dotsb + k + (k+1) &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\1 + 2 + \dotsb + k + (k+1) &= \frac{(k+1)(k+2)}{2} \end{align*} \] Which is exactly what we wanted to show.
For other healthy exercises in this same vein, one could prove that these summation formulas hold for all \(n \gt 0:\)
- \(\displaystyle 1^2 + 2^2 + 3^2 + \dotsb + n^2 = \frac{n(n+1)(2n+1)}{6}\,. \)
- \(\displaystyle 1^3 + 2^3 + 3^3 + \dotsb + n^3 = \left(\frac{n(n+1)}{2}\right)^2\,. \)
- \(\displaystyle 1^4 + 2^4 + 3^4 + \dotsb + n^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} \,.\)
For all positive integers \(n\) greater than three, it is true that \(2^n \lt n!\).
Solution
First notice that for \(n = 4\) the statement is true since \[2^4 = 16 \lt 24 = 4!\,.\]
Now, proceeding inductively, assume the statement is true for \(n = k\) for some specific positive integer \(k.\) I.e. we’re assuming that \(2^k \lt k!\). Our goal is to start from this fact and algebraically manipulate it to show that \(2^{k+1} \lt (k+1)!\) too. Here’s how we can do that: \[ \begin{align*} 2^k &\lt k! \\\mathbf{2} \times 2^k &\lt \mathbf{2} \times k! \\2 \times 2^k &\lt \mathbf{(k+1)} \times k! \quad\text{since } \mathbf{2 \lt (k+1)} \\2^{k+1} &\lt (k+1)! \end{align*} \] Which is exactly what we wanted to show.
For all positive integers \(n\), the number \(6^n+4\) is divisible by five.
Solution
Notice that for \(n = 1\) the statement is true since the number \(6^1+4\) is ten, which is divisible by five.
Now assume the statement is true for \(n = k\) for some specific positive integer \(k.\) I.e. we’re assuming that \(6^k +4\) is divisible by five. But what does this mean? This means there is some integer \(a\) such that \(5a = 6^k+4.\) Our goal is to start from this fact and algebraically manipulate it to show that \(6^{k+1} +4\) is divisible by five too, which means we need to find some other integer \(b\) such that \(5b = {6^{k+1} +4}.\) Here’s how we can do that: \[ \begin{align*} 5a &= 6^{k}+4 \\\mathbf{6}\times 5a &= \mathbf{6}\times\left(6^{k}+4\right) \\30a &= 6^{k+1}+24 \\30a &= 6^{k+1}+4 + 20 \\30a-20 &= 6{k+1}+4 \\5\left(6a-4\right) &= 6^{k+1}+4 \end{align*} \] which, for \(b = 6a-4\), is exactly what we wanted to show.
For other healthy exercises in this same vein, one could prove that these facts hold for all \(n \gt 0:\)
- The number \(4^n-1\) is divisible by three.
- Six divides \(7^n-1.\)
- Three divides \(n^3+2n.\)
- \(5^{2n+1} + 2^{2n+1}\) is divisible by \(7.\)