2 Assignment 2

2.1 Problem 1

claim

1 For any \(1 \leq k \leq n\) and \(0 {\lt} x {\lt} 1\)

\[ \binom {n}{k} x ^k \leq (1 + x) ^n \leq e ^{xn} \]

Proof ▼

First lets notice that for \(\forall x,k\) \(x^k{\gt}0\).now using the newton binomial we can get the following

\[ (1 + x) ^n=\sum ^n_{i=0}\binom {n}{i}x^i=\binom {n}{0}x^0+\binom {n}{1}x^1+\dots \underbrace{\binom {n}{k}x^k}_{\text{part of the sum}}+\binom {n}{k+1}x^{k+1}+\dots \binom {n}{n}x^n \]

because each one of the sum’s element is non negtive the following hold

\[ \binom {n}{k}x^k \leq (1 + x) ^n \]

using Bernoulli’s Inequality, for \(\forall n \in N \) and \(x{\gt}0\)

\[ 0{\lt} 1+x\leq \left(1+\frac{x}{n}\right)^n\xrightarrow [n\to \infty ]{} e^x \]

we can raise both side in power of n and we will get the complete formula

\[ \binom {n}{k} x ^k \leq (1 + x) ^n \leq e ^{xn} \]

claim 2.1

2 For any \(1 \leq k \leq n\) and \(0 {\lt} x {\lt} 1\)

\[ \ \binom {n}{k} \leq (\frac{en}{k})^k \]

Proof ▼

if k=n we Instantly get using the result of claim 1.

\[ 1=\binom {n}{n} \leq (\frac{en}{n})^n=e^n \]

now for \(k{\lt}n\) and using above inequality lets set \(0{\lt}x=\frac{k}{n}{\lt}1\)

\[ \binom {n}{k} (\frac{k}{n} )^k \leq e ^{\frac{k}{n}n} \Rightarrow \binom {n}{k}\leq (\frac{n}{k} )^ke^k=(\frac{en}{k} )^k \]

claim 2.2

3 For any \(1 \leq k \leq n\) and \(0 {\lt} x {\lt} 1\)

\[ \ \sum _{i=0}^k\binom {n}{i} \leq (\frac{en}{k})^k \]

Proof ▼

using the same way as above and claim 1 lets
\(k{\lt}n\) set \(0{\lt}x=\frac{k}{n}{\lt}1\)

\[ \sum ^n_{i=1}\binom {n}{i}(\frac{k}{n})^i\leq (1+\frac{k}{n})^n =\sum ^n_{i=0}\binom {n}{i}(\frac{k}{n})^i \leq e^{n\frac{k}{n}}=e^k \]

divide by \((\frac{k}{n})^k\)

\[ \ \sum ^n_{i=0}\binom {n}{i} \leq \sum ^n_{i=1}\binom {n}{i}(\frac{k}{n})^{i-k}\leq e^k(\frac{n}{k})^{-k}=(\frac{en}{k})^k \]

the first inequality holds because for \(i \leq k\) we get \(i-k{\lt}0\)

2.2 Problem 2.

Theorem 2.3

For all n \(\geq \)2, \(nlogn-n{\lt}log(n!){\lt}nlogn\) i.e \(\ln (n!)=\Theta (nln(n))\)

Proof ▼

First we note that \(\ln (n!)=\sum ^n_klnk\) and using Riemann sum approximation, and the fact that ln is a non-decreasing function on \([1,\infty )\) ,for all \(x\in [k,k+1)\) Integrating we get

\[ \ln (k) \leq ln(x) \leq \ln (k+1) \]

\[ \int _k^{k+1} \ln (k) dx \leq \int _k^{k+1} \ln (x) dx \leq \int _k^{k+1} \ln (k+1) dx . \]

Summing for k between 1 and n-1, we get

\[ \sum _{k=1}^{n-1} \ln (k) \leq \sum _{k=1}^{n-1} \int _k^{k+1} ln(x) dx = \int _1^{n} \ln (x) dx \leq \sum _{k=1}^{n-1} \ln (k+1) = \sum _{k=2}^{n} \ln (k) \]

adding ln(1),ln(n)

\[ \int _1^{n} \ln (x) dx + \ln (1)+ln(n) \leq \sum _{k=1}^{n-1} \ln (k) +\dfrac {ln(n)}{2}-\ln (1) \leq \int _1^{n} \ln (x) dx + \ln (n). \]

hence for

\[ \int _1^{n} \ln x dx = x\ln x -x|^n_1 = n\ln n - n +1 \]

we get

\[ n\ln (n) +\dfrac {ln(n)}{2} - n + 1 \leq \sum _{k=1}^{n} \ln k \leq n\ln -n + \dfrac {3\ln (n)}{2} + 1 \]

using the theorem above lets add to the of power e

\[ \exp (n\ln n - n + 1+\dfrac {\ln (n)}{2}) \leq \exp (\ln (n!))\leq \exp (\dfrac {3\ln (n)}{2}+n\ln n - n + 1) \]

\[ \\ \Leftrightarrow n!=\Theta (\sqrt{n}e(\frac{n}{e})^n) \]

2.3 Problem 3.

Let q(n) denote the number of ordered sets of positive integers whose sum is n, lets define \(Q\) such that \(Q\) is sequence size n of 1’s .

\[ Q: {1\nabla 1\nabla 1\nabla 1 \nabla \dots \nabla 1} \]

in total we looking at n times 1 and n-1 \(\nabla \). now lets say we have 2 operators \(\lbrace + , |\rbrace \) we can replace each time \(\nabla \) with ine of them, if we choose the \(+\) we "merge" both of the sums, but if we choose \(|\) we "slice" the set.hence the sum of \(Q\) will always stay n and each unique decision of choosen operator in order will give us unique ordered sets of positive, we can choose 2 operators total n-1 times, hence the number of ordered sets is

\[ q(n)=2^{n-1} \]

using the group \(Q\) define above, to find all the ordered sets size k hows sum is n, we can say that now we must replace k-1 of \(\nabla \) with \(|\), witch leaves us with total of k sets, and all the rest \(\nabla \) will get the \(+\) operator immediately. in total we have k-1 of \(|\) to rplace k-1 operator of \(\nabla \) from total \(n-1\nabla \) ,and by suuming all the option over k sizes of group we get.

\[ \sum _{k=1}^{n-1} \binom {n-1}{k-1}=\sum _{k=0}^{n} \binom {n-1}{k}=2^{n-1}=q(n) \]

2.4 Problem 4

Let p(n) denote the number of unordered sets of positive integers whose sum is n. lets define \(p_k(n)\) to be number of unordered sets of size k of positive integers whose sum is n.
using the result of problem 3 we know that for ordered set size k we have \(\binom {n-1}{k-1}\) option.if we looking at k different element we will have total of.

\[ p_k(n)=\dfrac {\binom {n-1}{k-1}}{k!} \]

but we might have some repeat numbers so its will be at most

\[ p_k(n)\geq \dfrac {\binom {n-1}{k-1}}{k!} \]

since we define q(n) s.t \(p(n)=\sum _k p_k(n)\) the following hold.

\[ p(n)=\sum _k p_k(n)\geq {\max }_{1 \geq k \geq n} \dfrac {\binom {n-1}{k-1}}{k!} \]

claim 2.4

there is an absolute constant \(c{\gt}0\) for which \(p(n) \geq e^{c\sqrt{n}}\)

Proof ▼

\[ p(n)=\geq {\max }_{1 \geq k \geq n} \dfrac {\binom {n-1}{k-1}}{k!} \geq \dfrac {\binom {n-1}{k-1}}{k!} =\frac{1}{k!}\frac{k}{n}\binom {n}{k} \]

using (*)\(\binom {n}{k} \geq (\frac{n}{k})^k\) (**)\(k!\geq ek(\frac{n}{k})^k\),

\[ \frac{1}{k!}\frac{k}{n}\binom {n}{k} \geq \underbrace{\frac{1}{ek(\frac{n}{k})^k}}_{**}\text{ } \underbrace{(\frac{n}{k})^k}_{*} \frac{k}{n} \]

for \(k=\sqrt{n}\)

\[ \frac{1}{e\sqrt{n}(\frac{n}{\sqrt{n}})^{\sqrt{n}}} (\frac{n}{\sqrt{n}})^{\sqrt{n}} \frac{\sqrt{n}}{n}=\frac{e^{\sqrt{n}}}{en}=\frac{e^{\sqrt{n}}}{e^{1+ \ln (n)}} \]

using the detention of limit ,for some \(1{\gt} \epsilon {\gt}0\)

\[ \frac{1+\ln (n)}{\sqrt{n}}\text{ }\overrightarrow {n\rightarrow \infty } \text{ }0\Rightarrow \frac{1+\ln (n)}{\sqrt{n}} {\lt} \epsilon \Rightarrow 1+\ln (n) {\gt} \epsilon \sqrt{n} \]

hence for \(c=1-\epsilon \) ,\(c{\gt}0\)

\[ \frac{e^{\sqrt{n}}}{e^{1+ \ln (n)}}\leq \frac{e^{\sqrt{n}}}{e^{\epsilon \sqrt{n}}}=e^{\sqrt{n}}-e^{\epsilon \sqrt{n}}=e^{c\sqrt{n}} \]

2.5 Problem 5.

Let \(\pi (m, n)\) denote the set of prime numbers in the interval [\(m,n\)].

we can see the following \([m,2m]\)

\[ \{ m+1,m+2,...,2m\} \]

now lets partition it to prime and and non prime element s.t

\[ \{ m+1,m+2,...,2m\} \setminus \pi (m+1,2m)= c(m+1,2m) \]

\[ n \in c(m+1,2m) \leftrightarrow \{ n\in [m,2m] \vee n \text{ is not prime} \} \]

now lets look at \(\binom {2m}{m}\)

\[ \binom {2m}{m}=\frac{2m(2m-1)...(m+1)}{m!}=\frac{1}{m!} \left(\prod \limits _{p\in \pi (m+1,2m)}p\right) \left(\prod \limits _{n\in c(m+1,2m)}n\right) \]

since for any \(m+1 \geq p \geq 2m , p\in \pi (m+1,2m)\)
i claim when \(p{\gt}m\) thus

\[ m! \hspace{-4pt}\not|\hspace{2pt}\left(\prod \limits _{p\in \pi (m+1,2m)}p\right) \]

and we get

\[ \binom {2m}{m}=\underbrace{ \dfrac {\left(\prod \limits _{n\in c(m+1,2m)}n\right)}{m!}}_{\geq 1}\left(\prod \limits _{p\in \pi (m+1,2m)}p\right) \geq \left(\prod \limits _{p\in \pi (m+1,2m)}p\right) \]

first lets notice that

\[ 4^{n}=2^{2n}=(1+1)^{2n}=\sum ^{2n}_{k=0}\binom {2n}{k} {\gt} \binom {2n}{n}, \]

\[ \text{and }2\cdot 2^{2n+1} {\gt} \binom {2n+1}{n} \Rightarrow \binom {2n+1}{n} \leq 2^{2n} \]

since its apper twice in the binomial coefficient, so both at scenario (even,odd) using the floor will give us bound for the given binom

\[ \left(\prod \limits _{p\in \pi (\lfloor m/2 \rfloor +1,2m)}p\right)\leq \binom {m}{\lfloor m/2 \rfloor } \leq 2^m \]

now lets use the floor function we can notice that

\[ \lfloor \lceil m/2^{2k} \rceil /2^k \rfloor =\lfloor m /2^{3k}\rfloor \]

hence for \(2m,m,m/2\)

\[ \left(\prod \limits _{p\in \pi (\lfloor m/4 \rfloor +1,\lceil m/2 \rceil )}p\right)\left(\prod \limits _{p\in \pi (\lceil m/2 \rceil +1,m)}p\right)\leq \binom {m}{\lfloor m/2 \rfloor }\binom {\lceil m/2 \rceil }{\lfloor m/4 \rfloor }\leq 2^m2^{\lfloor m/2 \rfloor } \]

we can apply it for all m,\(\lceil m/2 \rceil ,\lceil m/4 \rceil \)...

\begin{align} \left(\prod \limits _{p\in \pi (1,m)}p\right)= \left(\prod \limits _{p\in \pi (0+1,1)}p\right)\cdots \left(\prod \limits _{p\in \pi (\lceil m/2 \rceil +1,m)}p\right) \leq \\ {m \choose {\lfloor m/2 \rfloor }}{{\lceil m/2 \rceil } \choose {\lfloor m/4 \rfloor }}{{\lceil m/4 \rceil } \choose {\lfloor m/8 \rfloor }}\cdots \leq 2^m\cdot 2^{{\lfloor m/2 \rfloor }} \cdot 2^{{\lfloor m/4 \rfloor }} \cdots \end{align}

\[ \leq 2^{m + {\lfloor m/2 \rfloor } + {\lfloor m/4 \rfloor } + \cdots } \leq 2^{m(1 + 1/2 + 1/4 + \cdots ) } \leq 2^{2m} = 4^m \]

using line (1),(2) we sow above

\[ \log \left(\prod \limits _{p\in \pi (1,n)}p\right){\lt} \log (4^m) \Rightarrow O(2n\log 2) \]

\[ \log \left(\prod \limits _{p\in \pi (1,n)}p\right)= \sum _{ I=(\lceil 2i/i\rceil +1,i)i\in \pi (1,n)}\log \left(\prod \limits _{I}p\right) \leq \sum _{ I(\lceil 2i/i\rceil +1,i)i\in \pi (1,n)} \log \underbrace{{i \choose {\lfloor i/2 \rfloor }}}_{2^n\leq \binom {n}{2n}} \]

since \(2^n\leq \binom {n}{2n}\) and the result from sector 5.1 we can bound the following.

\[ \prod _{ I=(\lceil 2i/i\rceil +1,i)i\in \pi (1,n)}{{i \choose {\lfloor i/2 \rfloor }}} {\lt} \left(\prod \limits _{p\in \pi (1,n)}p\right)\leq (4^n) \]

log both sides

\[ \log (\prod _{ I=(\lceil 2i/i\rceil +1,i)i\in \pi (1,n)} \binom {i}{2i}) \leq |\pi (1,n)|\log (2^{\lg (n)\log 2}) {\lt} \log (4^n) \]

and we finality get

\[ |\pi (1,n)|\lg (n)\log 2 {\lt} 2n\log 2 \Leftrightarrow |\pi (1,n)|=O(\dfrac {n}{\log (n)}) \]

2.6 Problem 6.

claim 2.5

Every tournament \(T\) of order \(|V|=2^k\) contains an undominated set of size \(\leq k\).

Proof ▼

the base case of the induction is trivial for \(k=1,2\) lets assume the hypothesis hold for some for \(2^k\), now lets look at \(\hat{T}\) of order \(|V|=2^{k+1}\) lets look at the avarge \(\text{deg}_{out}\) i.e

\[ \frac{|E|}{|V|} = \dfrac {2^{k+1}(2^{k+1}-1)}{2*2^{k+1}}=2^k-\dfrac {1}{2} \]

hence exist some \(v \in |V|\) such that \(v_{\text{deg}_{out}}\geq 2^k \Rightarrow v_{\text{deg}_{in}} {\lt} 2^k\). now lets choose some \(2^k = |S|,\lbrace S:S \subseteq V \rbrace \) such that \(v\) dominated by any \(v_s\in S\). lets apply our induction assumption on sub-tournament \(S\), since exist \(\hat{S} \subseteq S\) size \( | \hat{S} | \leq k\) that not dominated by any other vertex\(\Rightarrow |\hat{S}\cup {v}|\leq k+1\) sub-set size \(k+1\) that not dominated in \(|T|=2^{k+1}\)

now lets look at some random tournament \(T\) that any \(e\in |E|\) have the same probability to be in each direction

\[ \Pr (e: u \rightarrow v)= \Pr (e: v \rightarrow u)=1/2 \]

\(\Rightarrow \) the probability that v is dominates on some u is \(1/2\)
\(\Rightarrow \) the probability v is dominates on \(S\subseteq V\) size \(k\) is \(1/2^k\)
\(\Rightarrow \) the probebilty that e dominated by some \(|S|=k\) is \((1-1/2^k)\)
\(\Rightarrow \) the probebilty that \(|T/S|=n-k\) dominated by some \(|S|=k\)
is \((1-1/2^k)^{n-k}\)
the expected number of group size k can bound from above with \(n \choose k\), hence when n holds

\[ \binom {n}{k}(1-1/2^k)^{n-k} {\lt}1 \]

then there is an n-vertex tournament so that every set of k vertices is dominated.
now lets use the property proved in Q(1) and we can bound the following for any \(k\geq 2\)

\[ \binom {n}{k}(1-1/2^k)^{n-k} \leq \underbrace{e^{-\frac{(n-k)}{2^k}}}_{Q1 \text{ and }1-k \leq e^k} \underbrace{\left(\dfrac {en}{k}\right)^k}_{\leq \binom {n}{k}}{\lt}1 \]

hence for \(n{\gt}k+2^k\cdot k^2\) the following hold .