From 56b740565fd6467564be28b5465ad24cccf71109 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Thu, 16 Jan 2020 21:24:46 -0500 Subject: moved comb hw --- tech-math/hw1.tex | 146 ------------------------------------------------------ 1 file changed, 146 deletions(-) delete mode 100644 tech-math/hw1.tex (limited to 'tech-math/hw1.tex') diff --git a/tech-math/hw1.tex b/tech-math/hw1.tex deleted file mode 100644 index 6f94327..0000000 --- a/tech-math/hw1.tex +++ /dev/null @@ -1,146 +0,0 @@ -\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 $ab0$ (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 -- cgit