aboutsummaryrefslogtreecommitdiff
path: root/tech-math/comb/hw1.tex
blob: 6f94327f12eee4e7f995033b76bb941a54806804 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
\input ws-form.tex

{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}}
Fall 2019\par\noindent
Homework 1\par\noindent
Due 09/03/2019} \smallskip \hrule \medskip
%#18
\question{%
Q1 (\#18) - How many integer solutions are there to the inequality $$x_1 + x_2 + x_3 + x_4 + x_5 \leq 782$$ provided that $x_1, x_2 > 0$, $x_3 \geq 0$, and $x_4, x_5 \geq 10$?
}{
This problem is equivalent to distributing 782 objects to 6 groups, each of which has identical restrictions on quantity (except the sixth, which follows $x_6 \geq 0$, in order to allow the integers to sum to less than or equal to $782$). The base case of all variables being strictly greater than 0 is ${781 \choose 5}$ because it can be modeled as choosing 5 distinct "gaps" of 781 gaps would split the 782 items into 6 groups. However, $x_3$ and $x_6$ can be equal to 0. Therefore, two fictitious objects are added to be chosen for group 3 and 6, which will be removed afterwards, making the enumeration ${783 \choose 5}$. The last irregular restriction of $x_4, x_5 \geq 10 \to x_4, x_5 > 9$ can be treated as distributing 18 total objects to the fourth and fifth groups before normal distribution. The final enumeration is ${765 \choose 5}$.
} \vfil
%#20 
\question{%
Q2 (\#20) - Give a combinatorial argument to prove the identity $k{n \choose k} = n{n-1 \choose k-1}$
}{
${n \choose k}$ is choosing k objects from a collection of n. ${1 \choose k} = k$ is choosing one object from a collection of k. Therefore, $k{n \choose k}$ is choosing k objects from n and one special object from the new collection.

$n{n-1 \choose k-1}$ is, similarly, choosing a special object for one collection from $n$ objects and $k-1$ from a remaining $n-1$. The chosen group of one special object and $k-1$ ordinary objects from a group of $n$ is equivalent to the first group and thus equal in numeration (the expressions are equal).
}\vfil\eject
%#25
\question{%
Q3 (\#25) - How many lattice paths from $(0,0)$ to $(17,12)$ are there that pass through $(7,6)$ and $(12,9)$?
}{
Because a lattice path only travels rightward and upward, each conformant path has a one-to-one correspondence to a set of lattice paths---one of which is between $(0,0)$ and $(7,6)$; one is between $(7,6)$ and $(12,9)$; the last is between $(12,9)$ and $(17,12)$.

Each lattice path's enumeration follows the form ${n+k \choose n}$ where $k$ is the $(n,k)$ is the difference in coordinates. By the basic enumeration theorem, the enumerations are multiplied---giving ${13 \choose 6}{8 \choose 3}{8 \choose 3}$.
}
\vfil
%#5
\question{%
Q4 (\#5) - Let $S$ be the set of substrings on the alphabet $\{0,1,2,3\}$ that do not contain $12$ or $20$ as a substring. Give a recursion for the number $h(n)$ of strings in $S$ of length $n$.
}{
$h(n) = 0$ for $n < 0$ because strings cannot have negative length.

$h(0) = 1$ because there is only the empty string.

$h(n) = 4h(n-1) - 2h(n-2) + h(n-3)$ for $n > 0$.
Starting with a string of length $n-1$, adding a character makes all potential strings of length $n$. But not all are valid. The number of invalid strings is determined by adding invalid substrings to the a smaller $n-2$ character long string. These have a one-to-one relation with invalid strings, but $h(n-1)$ has already ``caught some.'' Adding $120$ to a string of length $n-3$ will be removed from $h(n-1)$ because $12$ is caught, but it won't be removed from $h(n-2)$ because the $12$ hasn't appeared yet in its parsing. This gives the final value above.
} \vfil \eject
%#9
\question{%
Q5 (\#9) - For each formula, give both a proof using the Principle of Mathematical Induction and a combinatorial proof.
$$1^2+2^2+3^2+\ldots+n^2={n(n+1)(2n+1) \over 6} \leqno(a)$$
$${n \choose 0}2^0+{n \choose 1}2^1 + {n \choose 2}2^2 + \ldots + {n \choose n}2^n = 3^n \leqno(b)$$
}{
{\bf Part A; Induction:}

The statement is true for n=1. $1^2 = {1(1+1)(2(1)+1) \over 6} = {1\cdot2\cdot3 \over 6} = 1.$

If the statement is true for k-1, it is also true for k.
$$1^2+2^2+3^2+\ldots+(k-1)^2 = {(k-1)((k-1)+1)(2(k-1)+1) \over 6} = {(k-1)(k)(2k-1) \over 6}.$$
$$1^2+2^2+3^2+\ldots+(k-1)^2+k^2 = {k(k-1)(2k-1) \over 6} + k^2
 = {k(k-1)(2k-1) + 6k^2 \over 6}
 = {k(2k^2-3k+1) + 6k^2 \over 6}$$$$
 = {k(2k^2-3k+1+6k) \over 6}
 = {k(2k^2+3k+1) \over 6}
 = {k(2k+1)(k+1) \over 6}$$

{\bf Combinatorial:}

%${n(n+1)(2n+1) \over 6} = {n+1 \choose 2} + 2{n+1 \choose 3}$

Let there be a collection of $n$ indistinct objects. $1 \leq k \leq n$ objects are chosen. Of those $k$ objects, $0 \leq k_b < k$ objects are blue and $0 \leq k_r < k$ objects are red. An object can be both, one, or neither.
There are $1^2+2^2+3^2+\ldots+n^2$ possible groups because for all values of $k$ between $1$ and $n$, $k_b$ and $k_r$ each have $k$ possible values (giving, by the Basic Principle of Enumeration, a count of $k \cdot k = k^2$).

This can also be constructed as a collection of three positive integers and a boolean to order the lower two---if different. When all three integers are distinct, the count is ${n+1 \choose 3}$, or $2{n+1 \choose 3}$ with the boolean. If the lesser two are the same, the count is ${n+1 \choose 2}$ and the boolean is unimportant. The total number of groups is
$2{n+1 \choose 3}+{n+1 \choose 2} = {2(n+1)(n)(n-1) \over 6}+{(n+1)(n) \over 2} = {2(n+1)(n)(n-1) + 3(n+1)(n) \over 6} = {(2n-2)(n+1)(n) + 3(n+1)(n) \over 6} = {(2n-2+3)(n+1)(n) \over 6} = {(2n+1)(n+1)(n) \over 6}$

By double-counting the set of groups, $$1^2+2^2+3^2+\ldots+n^2={(2n+1)(n+1)(n) \over 6}$$ is true.
\medskip
{\bf Part B; Induction:}

$${n \choose 0}2^0+{n \choose 1}2^1 + {n \choose 2}2^2 + \ldots + {n \choose n}2^n = \sum_{i=0}^n{n \choose i}2^i$$

For $n=0$, the identity is true: ${0 \choose 0}2^0 = 1 = 1 = 3^0$. Assuming that it is true for $k$, it is also true for $k+1$.

$$\sum_{i=0}^k{k \choose i}2^i = 3^k$$
$$3\sum_{i=0}^k{k \choose i}2^i = 3(3^k)$$
$$3^{k+1} = 2\sum_{i=0}^k{k \choose i}2^i + \sum_{i=0}^k{k \choose i}2^i
= \sum_{i=0}^k{k \choose i}2^{i+1} + \sum_{i=0}^k{k \choose i}2^i
= \sum_{i=1}^{k+1}{k \choose i-1}2^i + \sum_{i=0}^k{k \choose i}2^{i} $$$$
= \sum_{i=0}^{k+1}{k \choose i-1}2^i - {k \choose -1}2^0 + \sum_{i=0}^{k+1}{n \choose i}2^i - {k \choose k+1}2^{k+1}
= \sum_{i=0}^{k+1}{k \choose i-1}2^i + \sum_{i=0}^{k+1}{k \choose i}2^i $$$$
= \sum_{i=0}^{k+1}\left({k \choose i-1} + {k \choose i}\right)2^i
= \sum_{i=0}^{k+1}{k+1 \choose i}2^i.
$$
By induction, the identity is true.
\medskip
{\bf Combinatorial:}

By the binomial theorem,
$$3^n = (2+1)^n = {n \choose 0}2^0 1^n + {n \choose 1}2^1 1^{n-1} + {n \choose 2}2^2 1^{n-2} + \ldots + {n \choose n}2^n 1^0 $$$$
= {n \choose 0}2^0 + {n \choose 1}2^1 + {n \choose 2}2^2 + \ldots + {n \choose n}2^n.$$

The binomial theorem works because in the expansion of $(x+y)^n$, there are ${n \choose k}$ ways to multiply to $x^ky^{n-k}$.
} \vfil
%#10
\question{%
Q6 (\#10) - Show that for all integers $n \geq 4$, $2^n < n!$.
}{
For $n=4$, $2^n < n!$ holds: $2^4 = 16 < 24 = 4!$.

Assuming that $2^n < n!$ is true for $k$, it is true for $k+1$.
$$2^{k+1} < (k+1)! \to 2\cdot 2^{k} < (k+1)k!$$
\par$2 < k+1$, and $ab<cd$ if $a<c$, $b<d$, and $a,b,c,d>0$ (all of which are true). QED
} \vfil \eject
%#16
\question{%
Q7 (\#16) - Give a proof by induction of the Binomial Theorem. How do you think it compares to the combinatorial argument given in Chapter 2? Binomial Theorem: {\it Let $x$ and $y$ be real numbers with $x$, $y$ and $x+y$ non-zero. Then for every non-negative integer $n$, $$(x+y)^n = \sum_{i=0}^{n} {n \choose i}x^{n-i}y^i.$$}
}{
For $n = 0$, $(x+y)^n = \sum_{i=0}^{n}{n \choose i}x^{n-i}y^i \to 1 = {0 \choose 0}1\cdot1 = 1$.

Assuming the statement to be true for $k$, it is also true for $k+1$:
$$(x + y)^k = \sum^k_{i=0}{k \choose i}x^{k-i}y^i.$$
$$(x + y)^k(x+y) = (x+y)\sum^k_{i=0}{k \choose i}x^{k-i}y^i.$$
$$(x + y)^{k+1} = x\sum^k_{i=0}{k \choose i}x^{k-i}y^i + y\sum^k_{i=0}{k \choose i}x^{k-i}y^i
 = \sum^k_{i=0}{k \choose i}x^{k+1-i}y^i + \sum^k_{i=0}{k \choose i}x^{k-i}y^{i+1} $$$$
 = \sum^{k}_{i=0}{k \choose i}x^{k+1-i}y^{i} + \sum^{k+1}_{i=i}{k \choose i-1}x^{k+1-i}y^i $$$$
 = -{k \choose k+1}y^{k+1}+\sum^{k+1}_{i=0} {k \choose i}x^{k+1-i}y^{i} - {k \choose -1}x^k + \sum^{k+1}_{i=0}{k \choose i-1}x^{k+1-i}y^i $$$$
 = \sum^{k+1}_{i=0} {k \choose i}x^{k+1-i}y^i + \sum^{k+1}_{i=0} {k \choose i-1}x^{k+1-i}y^i
 = \sum^{k+1}_{i=0} \left({k \choose i} + {k \choose i-1}\right)x^{k+1-i}y^i $$$$
 = \sum^{k+1}_{i=0} {k+1 \choose i}x^{k+1-i}y^i.
$$

The identity is true for $n \geq 0$. QED

This is much more convoluted than the combinatoric proof, and it lacks many of the key components the combinatoric proof uses to give a good intuitive understanding. However, it maintains some of the ideas of how the binomial theorem can be constructed---especially clear with knowledge of the combinatoric proof. When a term is ``added'' to the multiplicands, a new term forms because it's the sum of $y\cdot x^iy^{n-1-i}$ and $x\cdot x^{i-1}y^{n-i}$---a more incremental/recursive process than the combinatoric proof's very explicit ``one-time calculation.''
} \vfil
%#19
\question{%
Q8 (\#19) - Suppose that $x \in {\bf R}$ and $x > -1$. Prove that for all integers $n \geq 0$, $(1+x)^n \geq 1 + nx$.
}{
For $n=0$, $$(1+x)^0 \geq 1 + 0x \to 1 \geq 1.$$

Assuming it is true for $k$, it also is true for $k+1$:
$$(1+x)^k \geq 1 + kx.$$
$$(1+x)^k(1+x) \geq (1 + kx)(1+x).$$
$$(1+x)^{k+1} \geq 1 + (1+k)x + kx^2$$

$1 + (1+k)x + kx^2 \geq 1 + (1+k)x$ because $kx^2 > 0$, so
$$(1+x)^{k+1} \geq 1 + (1+k)x.$$

QED
} \vfil \eject
\bye