Aufgabe:
Zeigen Sie, dass gilt
$$r,s \in \mathbb{Q}^n: <rs> \ \leq \ <r> + <s>$$
Mit <*> ist die Codierungslänge gemeint, die wie folgt definiert ist:
Wenn r = p/q eine rationale Zahl (eindeutige Darstelllung, also p,q teilerfremd) ist, dann gilt: <r> := <p> + <q> und für eine ganze Zahl a gilt:
<a> := 1 + ⌈ log_2 ( |a| + 1) ⌉
Außerdem gilt für einen Vektor x ∈ ℚ^n: $$<x> := \sum \limits_{i=1}^{n} <x_i>$$
Zudem habe ich schon gezeigt:
Für rationale Zahl r gilt: $$|r| \leq 2^{<r>-1} -1$$
und für jeden Vektor x ∈ ℚ^n gilt: $$||x||_2 \leq ||x||_1 \leq 2^{<x>-n}$$
Lösungsversuch:
Ich bin soweit gekommen, jetzt komme ich allerdings nicht mehr weiter:
$$<rs> = <\sum \limits_{i=1}^{n}r_is_i> = \sum\limits_{i=1}^{n}<r_is_i>$$
Gibt es da irgendeinen Trick? Die Definiton mit der ganzen Zahl kann man ja leider auch nicht verwenden, da r_i und s_i aus ℚ sind.
