Discrete MathematicsAn Open Introduction

\(\frac{430\cdot 107}{2} = 23005\text{.}\)

1. \(n+2\) terms.
2. \(4n+2\text{.}\)
3. \(\frac{(4n+8)(n+2)}{2}\text{.}\)

1. \(2, 10, 50, 250, \ldots\) The sequence is geometric.
2. \(\frac{2 - 2\cdot 5^{25}}{-4}\text{.}\)

\(a_n = n^2 + 4n - 1\text{.}\)

1. The sequence of partial sums will be a degree 4 polynomial (its sequence of differences will be the original sequence).

2. The sequence of second differences will be a degree 1 polynomial - an arithmetic sequence.

1. \(4, 6, 10, 16, 26, 42, \ldots\text{.}\)

2. No, taking differences gives the original sequence back, so the differences will never be constant.

\(b_n = (n+3)n\text{.}\)

1. \(1, 2, 16,68, 364, \ldots\text{.}\)
2. \(a_n = \frac{3}{7}(-2)^n + \frac{4}{7}5^n\text{.}\)

1. \(a_2 = 14\text{.}\) \(a_3 = 52\text{.}\)
2. \(a_n = \frac{1}{6}(-2)^n + \frac{5}{6}4^n\text{.}\)

1. On the first day, your 2 mini bunnies become 2 large bunnies. On day 2, your two large bunnies produce 4 mini bunnies. On day 3, you have 4 mini bunnies (produced by your 2 large bunnies) plus 6 large bunnies (your original 2 plus the 4 newly matured bunnies). On day 4, you will have \(12\) mini bunnies (2 for each of the 6 large bunnies) plus 10 large bunnies (your previous 6 plus the 4 newly matured). The sequence of total bunnies is \(2, 2, 6, 10, 22, 42\ldots\) starting with \(a_0 = 2\) and \(a_1 = 2\text{.}\)

2. \(a_n = a_{n-1} + 2a_{n-2}\text{.}\) This is because the number of bunnies is equal to the number of bunnies you had the previous day (both mini and large) plus 2 times the number you had the day before that (since all bunnies you had 2 days ago are now large and producing 2 new bunnies each).

3. Using the characteristic root technique, we find \(a_n = a2^n + b(-1)^n\text{,}\) and we can find \(a\) and \(b\) to give \(a_n = \frac{4}{3}2^n + \frac{2}{3}(-1)^n\text{.}\)

1. Hint: \((n+1)^{n+1} > (n+1) \cdot n^{n}\text{.}\)

2. Hint: This should be similar to the other sum proofs. The last bit comes down to adding fractions.

3. Hint: Write \(4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}\)

4. Hint: one 9-cent stamp is 1 more than two 4-cent stamps, and seven 4-cent stamps is 1 more than three 9-cent stamps.

5. Careful to actually use induction here. The base case: \(2^2 = 4\text{.}\) The inductive case: assume \((2n)^2\) is divisible by 4 and consider \((2n+2)^2 = (2n)^2 + 4n + 4\text{.}\) This is divisible by 4 because \(4n +4\) clearly is, and by our inductive hypothesis, so is \((2n)^2\text{.}\)

Hint: This is a straight forward induction proof. Note you will need to simplify \(\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\) and get \(\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}\)

Hint: there are two base cases \(P(0)\) and \(P(1)\text{.}\) Then, for the inductive case, assume \(P(k)\) is true for all \(k \lt n\text{.}\) This allows you to assume \(a_{n-1} = 1\) and \(a_{n-2} = 1\text{.}\) Apply the recurrence relation.

Note that \(1 = 2^0\text{;}\) this is your base case. Now suppose \(k\) can be written as the sum of distinct powers of 2 for all \(1\le k \le n\text{.}\) We can then write \(n\) as the sum of distinct powers of 2 as follows: subtract the largest power of 2 less than \(n\) from \(n\text{.}\) That is, write \(n = 2^j + k\) for the largest possible \(j\text{.}\) But \(k\) is now less than \(n\text{,}\) and also less than \(2^j\text{,}\) so write \(k\) as the sum of distinct powers of 2 (we can do so by the inductive hypothesis). Thus \(n\) can be written as the sum of distinct powers of 2 for all \(n \ge 1\text{.}\)

Let \(P(n)\) be the statement, “every set containing \(n\) elements has \(2^n\) different subsets.” We will show \(P(n)\) is true for all \(n \ge 1\text{.}\) Base case: Any set with 1 element \(\{a\}\) has exactly 2 subsets: the empty set and the set itself. Thus the number of subsets is \(2= 2^1\text{.}\) Thus \(P(1)\) is true. Inductive case: Suppose \(P(k)\) is true for some arbitrary \(k \ge 1\text{.}\) Thus every set containing exactly \(k\) elements has \(2^k\) different subsets. Now consider a set containing \(k+1\) elements: \(A = \{a_1, a_2, \ldots, a_k, a_{k+1}\}\text{.}\) Any subset of \(A\) must either contain \(a_{k+1}\) or not. In other words, a subset of \(A\) is just a subset of \(\{a_1, a_2,\ldots, a_k\}\) with or without \(a_{k+1}\text{.}\) Thus there are \(2^k\) subsets of \(A\) which contain \(a_{k+1}\) and another \(2^{k+1}\) subsets of \(A\) which do not contain \(a^{k+1}\text{.}\) This gives a total of \(2^k + 2^k = 2\cdot 2^k = 2^{k+1}\) subsets of \(A\text{.}\) But our choice of \(A\) was arbitrary, so this works for any subset containing \(k+1\) elements, so \(P(k+1)\) is true. Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\)