diff options
| -rw-r--r-- | tech-math/hw1.tex | 146 | ||||
| -rw-r--r-- | ws-form.tex | 4 |
2 files changed, 148 insertions, 2 deletions
diff --git a/tech-math/hw1.tex b/tech-math/hw1.tex new file mode 100644 index 0000000..6f94327 --- /dev/null +++ b/tech-math/hw1.tex @@ -0,0 +1,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 diff --git a/ws-form.tex b/ws-form.tex index d446912..debafd0 100644 --- a/ws-form.tex +++ b/ws-form.tex @@ -1,10 +1,10 @@ \input color %allows colored answers \def\underline#1{\vbox{\hbox{#1}\vskip 1pt\hrule\vskip-1pt}} \long\def\question#1#2{%question and answer -\par #1 +\par\noindent #1 \bigskip -{\color{red}% +{\color{blue}% #2 }\vfil } |