# Harrison Chapman

## Math 301: Homework 2

Due: Friday, September 13, 2019
1. 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:

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$$.

2. 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:

So we have proved the statement for $$n = k+1$$, and by induction we conclude that it holds for all natural numbers $$n$$.

3. 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}$$.

1. 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)$$

2. 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$$.

4. 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.