2 Assignment 2

2.1 Problem 1

claim

1 For any $1 \leq k \leq n$ and $0 < x < 1$

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

Proof ▼

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

(1 + x)^{n} = \sum_{i = 0}^{n} (\binom{n}{i}) x^{i} = (\binom{n}{0}) x^{0} + (\binom{n}{1}) x^{1} + \dots \underset{part of the sum}{\underset{⏟}{(\binom{n}{k}) x^{k}}} + (\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 > 0$

0 < 1 + x \leq {(1 + \frac{x}{n})}^{n} \to_{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^{x n}

claim 2.1

2 For any $1 \leq k \leq n$ and $0 < x < 1$

(\binom{n}{k}) \leq (\frac{e n}{k})^{k}

Proof ▼

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

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

now for $k < n$ and using above inequality lets set $0 < x = \frac{k}{n} < 1$

(\binom{n}{k}) (\frac{k}{n})^{k} \leq e^{\frac{k}{n} n} \Rightarrow (\binom{n}{k}) \leq (\frac{n}{k})^{k} e^{k} = (\frac{e n}{k})^{k}

claim 2.2

3 For any $1 \leq k \leq n$ and $0 < x < 1$

\sum_{i = 0}^{k} (\binom{n}{i}) \leq (\frac{e n}{k})^{k}

Proof ▼

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

\sum_{i = 1}^{n} (\binom{n}{i}) (\frac{k}{n})^{i} \leq (1 + \frac{k}{n})^{n} = \sum_{i = 0}^{n} (\binom{n}{i}) (\frac{k}{n})^{i} \leq e^{n \frac{k}{n}} = e^{k}

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

\sum_{i = 0}^{n} (\binom{n}{i}) \leq \sum_{i = 1}^{n} (\binom{n}{i}) (\frac{k}{n})^{i - k} \leq e^{k} (\frac{n}{k})^{- k} = (\frac{e n}{k})^{k}

the first inequality holds because for $i \leq k$ we get $i - k < 0$

2.2 Problem 2.

Theorem 2.3

For all n $\geq$ 2, $n l o g n - n < l o g (n!) < n l o g n$ i.e $\ln (n!) = Θ (n l n (n))$

Proof ▼

First we note that $\ln (n!) = \sum_{k}^{n} l n k$ 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 l n (x) \leq \ln (k + 1)

\int_{k}^{k + 1} \ln (k) d x \leq \int_{k}^{k + 1} \ln (x) d x \leq \int_{k}^{k + 1} \ln (k + 1) d x .

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} l n (x) d x = \int_{1}^{n} \ln (x) d x \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) d x + \ln (1) + l n (n) \leq \sum_{k = 1}^{n - 1} \ln (k) + \frac{l n (n)}{2} - \ln (1) \leq \int_{1}^{n} \ln (x) d x + \ln (n) .

hence for

\int_{1}^{n} \ln x d x = x \ln x - x |_{1}^{n} = n \ln n - n + 1

we get

n \ln (n) + \frac{l n (n)}{2} - n + 1 \leq \sum_{k = 1}^{n} \ln k \leq n \ln - n + \frac{3 \ln (n)}{2} + 1

using the theorem above lets add to the of power e

\exp (n \ln n - n + 1 + \frac{\ln (n)}{2}) \leq \exp (\ln (n!)) \leq \exp (\frac{3 \ln (n)}{2} + n \ln n - n + 1)

\Leftrightarrow n! = Θ (\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 ${+, |}$ 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) = \frac{(\binom{n - 1}{k - 1})}{k!}

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

p_{k} (n) \geq \frac{(\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} \frac{(\binom{n - 1}{k - 1})}{k!}

claim 2.4

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

Proof ▼

p (n) =\geq {max}_{1 \geq k \geq n} \frac{(\binom{n - 1}{k - 1})}{k!} \geq \frac{(\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 e k (\frac{n}{k})^{k}$ ,

\frac{1}{k!} \frac{k}{n} (\binom{n}{k}) \geq \underset{* *}{\underset{⏟}{\frac{1}{e k (\frac{n}{k})^{k}}}} \underset{*}{\underset{⏟}{(\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}}}{e n} = \frac{e^{\sqrt{n}}}{e^{1 + \ln (n)}}

using the detention of limit ,for some $1 > ϵ > 0$

\frac{1 + \ln (n)}{\sqrt{n}} \vec{n \to \infty} 0 \Rightarrow \frac{1 + \ln (n)}{\sqrt{n}} < ϵ \Rightarrow 1 + \ln (n) > ϵ \sqrt{n}

hence for $c = 1 - ϵ$ , $c > 0$

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

2.5 Problem 5.

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

we can see the following $[m, 2 m]$

{m + 1, m + 2, . . ., 2 m}

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

{m + 1, m + 2, . . ., 2 m} ∖ π (m + 1, 2 m) = c (m + 1, 2 m)

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

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

(\binom{2 m}{m}) = \frac{2 m (2 m - 1) . . . (m + 1)}{m!} = \frac{1}{m!} (\prod_{p \in π (m + 1, 2 m)} p) (\prod_{n \in c (m + 1, 2 m)} n)

since for any $m + 1 \geq p \geq 2 m, p \in π (m + 1, 2 m)$
i claim when $p > m$ thus

m! |̸ (\prod_{p \in π (m + 1, 2 m)} p)

and we get

(\binom{2 m}{m}) = \underset{\geq 1}{\underset{⏟}{\frac{(\prod_{n \in c (m + 1, 2 m)} n)}{m!}}} (\prod_{p \in π (m + 1, 2 m)} p) \geq (\prod_{p \in π (m + 1, 2 m)} p)

first lets notice that

4^{n} = 2^{2 n} = (1 + 1)^{2 n} = \sum_{k = 0}^{2 n} (\binom{2 n}{k}) > (\binom{2 n}{n}),

and 2 \cdot 2^{2 n + 1} > (\binom{2 n + 1}{n}) \Rightarrow (\binom{2 n + 1}{n}) \leq 2^{2 n}

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

(\prod_{p \in π (⌊ m / 2 ⌋ + 1, 2 m)} p) \leq (\binom{m}{⌊ m / 2 ⌋}) \leq 2^{m}

now lets use the floor function we can notice that

⌊ ⌈ m / 2^{2 k} ⌉ / 2^{k} ⌋ = ⌊ m / 2^{3 k} ⌋

hence for $2 m, m, m / 2$

(\prod_{p \in π (⌊ m / 4 ⌋ + 1, ⌈ m / 2 ⌉)} p) (\prod_{p \in π (⌈ m / 2 ⌉ + 1, m)} p) \leq (\binom{m}{⌊ m / 2 ⌋}) (\binom{⌈ m / 2 ⌉}{⌊ m / 4 ⌋}) \leq 2^{m} 2^{⌊ m / 2 ⌋}

we can apply it for all m, $⌈ m / 2 ⌉, ⌈ m / 4 ⌉$ ...

\begin{array}{r} (\prod_{p \in π (1, m)} p) = (\prod_{p \in π (0 + 1, 1)} p) \dots (\prod_{p \in π (⌈ m / 2 ⌉ + 1, m)} p) \leq \\ (\binom{m}{⌊ m / 2 ⌋}) (\binom{⌈ m / 2 ⌉}{⌊ m / 4 ⌋}) (\binom{⌈ m / 4 ⌉}{⌊ m / 8 ⌋}) \dots \leq 2^{m} \cdot 2^{⌊ m / 2 ⌋} \cdot 2^{⌊ m / 4 ⌋} \dots \end{array}

\leq 2^{m + ⌊ m / 2 ⌋ + ⌊ m / 4 ⌋ + \dots} \leq 2^{m (1 + 1 / 2 + 1 / 4 + \dots)} \leq 2^{2 m} = 4^{m}

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

\log (\prod_{p \in π (1, n)} p) < \log (4^{m}) \Rightarrow O (2 n \log 2)

\log (\prod_{p \in π (1, n)} p) = \sum_{I = (⌈ 2 i / i ⌉ + 1, i) i \in π (1, n)} \log (\prod_{I} p) \leq \sum_{I (⌈ 2 i / i ⌉ + 1, i) i \in π (1, n)} \log \underset{2^{n} \leq (\binom{n}{2 n})}{\underset{⏟}{(\binom{i}{⌊ i / 2 ⌋})}}

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

\prod_{I = (⌈ 2 i / i ⌉ + 1, i) i \in π (1, n)} (\binom{i}{⌊ i / 2 ⌋}) < (\prod_{p \in π (1, n)} p) \leq (4^{n})

log both sides

\log (\prod_{I = (⌈ 2 i / i ⌉ + 1, i) i \in π (1, n)} (\binom{i}{2 i})) \leq | π (1, n) | \log (2^{\lg (n) \log 2}) < \log (4^{n})

and we finality get

| π (1, n) | \lg (n) \log 2 < 2 n \log 2 \Leftrightarrow | π (1, n) | = O (\frac{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 ${deg}_{o u t}$ i.e

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

hence exist some $v \in | V |$ such that $v_{{deg}_{o u t}} \geq 2^{k} \Rightarrow v_{{deg}_{i n}} < 2^{k}$ . now lets choose some $2^{k} = | S |, {S : S \subseteq V}$ 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 \to v) = Pr (e : v \to 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 $(\binom{n}{k})$ , hence when n holds

(\binom{n}{k}) (1 - 1 / 2^{k})^{n - k} < 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 \underset{Q 1 and 1 - k \leq e^{k}}{\underset{⏟}{e^{- \frac{(n - k)}{2^{k}}}}} \underset{\leq (\binom{n}{k})}{\underset{⏟}{{(\frac{e n}{k})}^{k}}} < 1

hence for $n > k + 2^{k} \cdot k^{2}$ the following hold .