1

(a)For $m,n \in \mathbb{N}$, $m<n$ and $k=0, ..., m$:

$$\frac{1}{m^k} \binom{m}{k} \leq \frac{1}{n^k} \binom{n}{k}$$

(b)For $n\in \mathbb{N}$ and $k=1, ..., n:$

$$\frac{1}{n^k} \binom{n}{k} \leq \frac{1}{k!} \leq \frac{1}{2^{k-1}}$$

(c)Show that for $n \in \mathbb{N}:$

$$2 \leq (1+ \frac{1}{n})^n < 3$$

Use (a) and the binomial theorem for (b). Use the following for (c): $$\sum_{j=0}^{n}q^j=\frac{1-q^{n+1}}{1-q}$$

I've already proven (a) thanks to @trancelocation. Now I got stuck on (b) and (c).

(b) I don't know how to use (a) and the binomial theorem here.

$\frac{1}{n^k} \binom{n}{k} \leq \frac{1}{k!} \leq \frac{1}{2^{k-1}} \Leftrightarrow \frac{n!}{n^k*(n-k)!* k!}\leq \frac{1}{k!} \leq \frac{1}{2^{k-1}} \Leftrightarrow \frac{n!}{n^k*(n-k)!}\leq 1 \leq \frac{k!}{2^{k-1}}$

Now I have to show: $\frac{n!}{n^k*(n-k)!}\leq 1$ and $1 \leq \frac{k!}{2^{k-1}}$

$\frac{n!}{n^k*(n-k)!} = \frac{n*(n-1)*...*(n-k+1)*[(n-k)*...*1]}{n^k*[(n-k)*...*1]}=\frac{n*...*(n-k+1)}{n^k}=\frac{n}{n}*\frac{n-1}{n}*...*\frac{n-k+1}{n} \leq 1$.

The first factor is $1$. Starting from the second factor their value gets smaller, so the entire term gets smaller then $1$.

I tried to do it like this:

for $i=0, ..., n$: $\frac{n-i}{n} \leq 1 \Leftrightarrow n-i \leq n \Leftrightarrow 0 \leq i$

For the second part:

$\frac{k!}{2^{k-1}} \geq 1 \Leftrightarrow \frac{k!}{2^k*2} \geq 1 \Leftrightarrow \frac{k!}{2^k} \geq 2\Leftrightarrow \frac{k}{2}*\frac{k-1}{2}*\frac{k-2}{2}*...*\frac{1}{2} \geq 2$

So for $\frac{k-j}{2} \geq 2$, with $j=0, ..., k-1$

$\frac{k-j}{2} \geq 2 \Leftrightarrow k-j \geq 4$

This doesn't seem to help at all.

(c)$2 \leq (1+ \frac{1}{n})^n < 3$

I didn't know how to start at c) at all. The provided formula doesn't help me.

Sumanta
  • 9,534
franz3
  • 449
  • 3
  • 11

1 Answers1

1

For the part (b) you had the right idea but you made a little mistake. Here is the correct one:

$\frac{k!}{2^{k-1}} \geq 1 \Leftrightarrow \frac{2 \cdot k!}{2^k} \geq 1 \Leftrightarrow \frac{k!}{2^k} \geq \frac12\Leftrightarrow \frac{k}{2}*\frac{k-1}{2}*\frac{k-2}{2}*...*\frac{1}{2} \geq \frac12$

or

$\frac{k}{2}*\frac{k-1}{2}*\frac{k-2}{2}*...*\frac{3}{2}*\frac{2}{2} \geq 1$

and since all factors on the LHS are $≥1$ this is true.

For part (c), we need to solve two inequalities. First, let us rewrite the geometric series $\sum_{j=0}^{n}q^j=\frac{1-q^{n+1}}{1-q}$ as $q^n = \frac1q (1 - (1-q)\sum_{j=0}^{n}q^j)$. Using $q = 1 + \frac1n$ and $(1 + \frac1n)^j \ge 1$ gives $$ (1 + \frac1n)^n = \frac{1}{1 + \frac1n} (1 +\frac1n\sum_{j=0}^{n}(1 + \frac1n)^j) \\ = \frac{1}{1 + \frac1n} (1 +\frac1n+\frac1n\sum_{j=1}^{n}(1 + \frac1n)^j) = \frac{1 +\frac1n}{1 + \frac1n} +\frac1n\sum_{j=1}^{n}\frac{(1 + \frac1n)^j}{1 + \frac1n}\\ = 1 + \frac1n\sum_{j=0}^{n-1}(1 + \frac1n)^j \ge 1 + \frac{n}{n} =2 $$ which establishes the left inequality. For the right inequality, use the binomial theorem, then (b), then the given geometric series, to write $$ (1 + \frac1n)^n = \sum_{k=0}^{n} \binom{n}{k} \frac{1}{n^k} = 1 + \sum_{k=1}^{n} \binom{n}{k} \frac{1}{n^k}\\ \le 1 + \sum_{k=1}^{n} \frac{1}{2^{k-1}} = 1 + \sum_{k=0}^{n-1} \frac{1}{2^{k}} = 1 + \frac{1 - (\frac12)^n}{1 - \frac12} < 1 + \frac{1 }{1 - \frac12} = 3 $$

Andreas
  • 15,175
  • In part (c), the first part, you wrote: $$\frac{1}{1 + \frac1n} (1 +\frac1n+\frac1n\sum_{j=1}^{n}(1 + \frac1n)^j)\ = 1 + \frac1n\sum_{j=0}^{n-1}(1 + \frac1n)^j \ge 1 + \frac{n}{n} =2$$ Which k did you pull out of the sum? Because I'm stuck at: $$\frac{1}{1 + \frac1n} (1 +\frac1n+\frac1n\sum_{j=1}^{n}(1 + \frac1n)^j)=1+\frac{1}{n(1 + \frac{1}{n})} (\sum_{j=1}^{n}(1 + \frac1n)^j)=1+\frac{1}{n+1} *(\sum_{j=1}^{n}(1 + \frac1n)^j)$$ – franz3 Nov 08 '19 at 06:20
  • In part(c), part 2, you wrote:$$(1 + \frac1n)^n =\sum_{k=0}^{n} \binom{n}{k} \frac{1}{n^k} $$ I got until here: $$(1 + \frac1n)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k(\frac{1}{n})^{n-k} = \sum_{k=0}^{n} \binom{n}{k} \frac{1^{n-k}}{n^{n-k}}=\sum_{k=0}^{n} \binom{n}{k} \frac{1}{n^nn^{-k}}=\sum_{k=0}^{n} \binom{n}{k} \frac{n^k}{n^n}$$ How did you get to: $$\sum_{k=0}^{n} \binom{n}{k} \frac{1}{n^k} $$ – franz3 Nov 08 '19 at 06:34
  • 1
    For yor first question: I pulled $j=0$ out of the sum. I added an extra line in the main text to show the arithemetics. – Andreas Nov 08 '19 at 08:20
  • 1
    For your second question: it is as well $(1 + \frac1n)^n = \sum_{k=0}^{n} \binom{n}{k} (\frac{1}{n})^{k} 1^{n-k}$ so there is nothing to do. – Andreas Nov 08 '19 at 08:22
  • Thanks for your clarification. I've got another question for (b): Don't I have to prove here that every factor is $\leq 1$: $$\frac{n}{n}\frac{n-1}{n}...*\frac{n-k+1}{n} \leq 1$$ I tried to do it like this: for $i=0, ..., n: \frac{n-i}{n} \leq 1 \Leftrightarrow n-i \leq n \Leftrightarrow i \geq 0$ Is this enough? – franz3 Nov 08 '19 at 16:13
  • And in the second part of (b) I have to prove then that every factor is $\geq 1$. $$\frac{k}{2}\frac{k-1}{2}\frac{k-2}{2}...\frac{3}{2}*\frac{2}{2} \geq 1$$ for $j = 0, ..., k-2: \frac{k-j}{2} \geq 1 \Leftrightarrow k-j \geq 2$. This doesn't seem to prove that every factor is $\geq 1$. – franz3 Nov 08 '19 at 16:16
  • Yes but all of these conditions do hold !: all factors in the first part of (b) are $\le1$ and $\ge 1$ in the second part. – Andreas Nov 08 '19 at 19:47