Prove that \(5n + 5 \le n^2\) for all integers \(n \ge 6\).
Proof. We prove this by induction. The base case, where \(n = 6\), is true as \(5n+5 = 35\) and \(n^2 = 36\) and we see \(35 \le 36\).
As an inductive hypothesis, assume for some \(6 \le n = k \in \mathbb N\) that \(5k + 5 \le k^2\). Then for \(n = k+1\) we consider:
\[\begin{align*} 5(k+1) + 5 &= 5k + 5 + 5 \\ &\le k^2 + 5 & \textrm{inductive hypothesis} \\ &\le k^2 + 12 + 1 \\ &\le k^2 + 2k + 1 & \textrm{as } 6 \le k \Rightarrow 12 \le 2k \\ &= (k+1)^2 \end{align*}\]So we have proved the statement for \(n = k+1\), and by induction we conclude that it holds for all natural numbers \(n \ge 6\).
Prove that \(1^2 + 2^2 + 3^2 + \cdots + (n-1)^2 + n^2 = \frac{n(n+1)(2n+1)}6\) for all integers \(n \ge 1\).
Proof. We prove this by induction. The base case, where \(n = 1\), is true as \(1^2 = 1\) and \(\frac{1(1+1)(2+1)}{6} = 1\) and we see \(1 = 1\).
As an inductive hypothesis, assume for some \(n = k \in \mathbb N\) that \(1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}\). Then for \(n = k+1\) we consider:
\[\begin{align*} 1^2 + 2^2 + \cdots k^2 + (k+1)^2 &= (1^2 + 2^2 + \cdots k^2) + (k+1)^2 \\ &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 & \textrm{inductive hypothesis} \\ &= (k+1)\left( \frac{k(2k+1)}{6} + (k+1) \right) \\ &= (k+1)\left( \frac{2k^2+7k + 6)}{6} \right)\\ &= \frac{(k+1)(k+2)(2k+3)}{6} \\ &= \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} \end{align*}\]So we have proved the statement for \(n = k+1\), and by induction we conclude that it holds for all natural numbers \(n\).
An octal number (that is, a number written in base 8), is a number written with digits from the set \(\{0,1,2,3,4,5,6,7\}\). How many octal numbers of 11 digits are there?
By our theorem on sequences; there are 8 letters in our alphabet and we are using 11 for a word and the answer is \(8^{11}\).
How many strings of length 5 can be written using the letters \(\{a,b,c,d,e,f\}\) if no two consecutive letters can be the same? For example, we’d count \(adcde\) but not \(acdde\).
Notice that all we have to do in order to avoid having two letters in a row is forbid the previous letter in the word. The first letter doesn’t have this problem and can be any letter of the 6 in our alphabet. For the remaining 4, we have 5 choices. So, the answer is \(6(5^4)\)
How many strings of length 5 can be written using the letters \(\{a,b\}\) if no three consecutive letters can be the same? For example, we’d count \(ababa\) and \(abbaa\), but not \(aaaba\).
This question is way harder, since we can’t really describe the condition of 3 letters in a row the same way. The best way to solve this question so far is to enumerate all the possibilities, and we find \(16\).
Show that a nonempty set \(S\) has the same number of odd subsets (that is, subsets with an odd number of elements) as even subsets. (Hint: Start with a set \(S\) with odd cardinality and find a bijective correspondence.)
\(S\) is nonempty, so say \(x \in S\) is an element.
Consider any subset \(T \subseteq S\). Suppose \(T\) is odd. If \(x \in T\), then \(T \setminus \{x\} \subseteq S\) is even. If \(x \not\in T\), then \(T \cup \{x\} \subseteq S\) is even. Either way, we have associated to each odd set \(T \subseteq S\) an even subset of \(S\). By following the procedure in reverse, we can see that each associated even subset is unique, so this describes a bijective correspondence. So \(S\) has the same number of odd and even subsets.