path: root/tech-math/comb/hw1.tex

\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