DisMat UE 02

ex2-0.pdf
Diskrete_Mathematik_Lösung_UE_02-0.pdf

2.1

Show

t^{n} = k_{1}, ..., k_{t} \sum (k _{1} , ... , k _{t} n)

use multinomial therom

(x_{1} + ... + x_{t})^{n} = k_{1} + ... + k_{t} = n \sum (k _{1} , ... , k _{t} n) x_{1}^{k_{1}} ... x_{t}^{k_{t}}

If we set $x_{1}, ... x_{t} = 1$
$(x_{1}, + ... + x_{t})^{n}$ becomes $(1_{1}, + ... + 1_{t})^{n} = t^{n}$
$k_{1} + ... + k_{t} = n \sum (k _{1} , ... , k _{t} n) x_{1}^{k_{1}}, ..., x_{t}^{k_{t}}$ becomes
$k_{1} + ... + k_{t} = n \sum (k _{1} , ... , k _{t} n) 1_{1}^{k_{1}} ... 1_{t}^{k_{t}} = k_{1} + ... + k_{t} = n \sum (k _{1} , ... , k _{t} n)$

2.2

Show

k_{1}, ..., k_{t} \sum (- 1)^{k_{2} + k_{4} + k_{6} + ...} (k _{1} , ... , k _{t} n) = {01 if t is even, if t is odd.

use multinomial therom

(x_{1} + ... + x_{t})^{n} = k_{1} + ... + k_{t} = n \sum (k _{1} , ... , k _{t} n) x_{1}^{k_{1}} ... x_{t}^{k_{t}}

If we set $x_{1} = 1, x_{2} = - 1, x_{3} = 1, ...$

x_{1}^{k_{1}} x_{2}^{k_{2}} x_{3}^{k_{3}}, ... = 1^{k_{1}} (- 1)^{k_{2}} 1^{k_{3}}, ... = (- 1)^{k_{2} + k_{4} + k_{6} + ...}

k_{1} + ... + k_{t} = n \sum (- 1)^{k_{2} + k_{4} + k_{6} + ...} (k _{1} , ... , k _{t} n) = (1 - 1 + 1 - ...)^{n} = {(0)^{n} (1)^{n} if t is even, if t is odd.

For all $n > 0$

2.4

Let $k$ and $N$ be positive integers.
Show that there exists a unique integer $1 \leq m \leq k$ , and unique integers $x_{m}, ..., x_{k}$ , such that $x_{k} > x_{k - 1} > \cdot\cdot\cdot > x_{m} \geq m$ , and we have the decomposition

N = (k x _{k}) + (k - 1 x _{k - 1}) + ... + (m x _{m}) = i = m \sum k (i x _{i})

Existance

proof by induction

Assumption

Choose largest $x_{k}$ such that

(k x _{k}) \leq N

There is always at least one for $N \geq 1$ because

(k k) = 1 \leq N

For $i$ with $m \leq i < k$ define

N_{i} := N_{i + 1} - (i + 1 x _{i + 1})

and
$N_{k} := N$

$i \leftarrow k - 1$

Repeat for $i \leftarrow i - 1$ while $N_{i} > 0$

choose next largest $x_{i}$ going down such that

(i x _{i}) \leq N_{i}

Once $N_{i} = 0$

this $i$ is $m$

Proof: Induction takes at most $k$ steps

every $(i x _{i}) \geq 1$

Proof: strict inequalities $x_{k} > x_{k - 1} > \cdot\cdot\cdot > x_{m} \geq m$

But we chose $x_{i}$ maximality so

(i x _{i}) \leq N_{i} < (i x _{i} + 1)

Using Pascals identity

(i x _{i} + 1) = (i x _{i}) + (i - 1 x _{i})

N_{i} < (i x _{i}) + (i - 1 x _{i})

(i - 1 x _{i - 1}) \leq N_{i - 1} = N_{i} - (i x _{i}) < (i - 1 x _{i})

thus
$x_{i - 1}$ must be smaller than $x_{i}$

Transclude of DisMat-UE-02-4.excalidraw

Quartz 4

Explorer

DisMat UE 02

2.1

2.2

2.4

Existance

Assumption

Repeat for $i \leftarrow i - 1$ while $N_{i} > 0$

Once $N_{i} = 0$

Proof: Induction takes at most $k$ steps

Proof: strict inequalities $x_{k} > x_{k - 1} > \cdot\cdot\cdot > x_{m} \geq m$

Graph View

Table of Contents

Backlinks

Quartz 4

Explorer

DisMat UE 02

2.1

2.2

2.4

Existance

Assumption

Repeat for i←i−1 while Ni​>0

Once Ni​=0

Proof: Induction takes at most k steps

Proof: strict inequalities xk​>xk−1​>⋅⋅⋅>xm​≥m

Graph View

Table of Contents

Backlinks

Repeat for $i \leftarrow i - 1$ while $N_{i} > 0$

Once $N_{i} = 0$

Proof: Induction takes at most $k$ steps

Proof: strict inequalities $x_{k} > x_{k - 1} > \cdot\cdot\cdot > x_{m} \geq m$