Folge abschätzen und mit Induktion beweisen

Question

Aufgabe: Man soll eine Folge abschätzen und mit Induktion beweisen.

Es gilt S_n = 3n - 1

Paar Sachen überspringe ich und komme zum wichtigen Teil:

Unter Annahme der Korrektheit für alle n = $2^{i}$, i ≤ j, n > 0 ergibt sich der Induktionsschritt von n =  $2^{i}$ nach m = 2n =  $2^{i+1}$

T_m = 2 * T_m/2 + 1 ≤ 2 S_m/2 + 1 = 2 * (3n/2-1) + 1 = 3n-2+1 = 3n-1

Kann mir einer erklären, wie man von S_m/2 auf (3n/2-1) und von 2 * (3n/2-1) auf 3n-2 kommt ?

Comments

Wie lautet denn die Behauptung, deren Beweis

dich grübeln lässt?

---

Das steht eigentlich schon in der Frage. Man soll halt 3n - 1 beweisen und mich interessiert halt wie man in den Lösungen von S_m/2 auf (3n/2-1) kommt

---

Man soll halt 3n - 1 beweisen

Das ist ein Term. Den kann man nicht beweisen.
Wie lautet die AUSSAGE, um deren Beweis es geht?

---

In der Aufgabe ist das eine Folge S_{n =} 3n - 1 und man soll T_n ≤ S_n beweisen. Die ganze Aufgabe hier zu erläutern wäre aus Zeitgründen zu lang. Mich interessiert halt nur wie man in den Lösungen von S_m/2 auf (3n/2-1) kommt, wenn keiner eine Idee hat, lerne ich eben auf Lücke.

---

Wenn du mir noch sagst, was $T_n$ ist, muss ich nicht so
im Nichts herumstochern.

Das Ganze wirkt ein wenig wie aus dem
"Dunstkreis" der Collatz-Vermutung.

---

Warum teilst du uns nicht mit, wie $T_n$ definiert ist?
Ich habe nicht ewig Zeit, mich mit dem Problem zu beschäftigen!

---

Weil ich wohl meinen Dozenten mit der Aufgabe betrauen werde, trotzdem danke für die Mühe.

Answer 1

von 2 * (3n/2-1) auf 3n-2

wohl so:

$2 \cdot ( \frac{3n}{2}-1) = 2 \cdot \frac{3n}{2} - 2 \cdot 1 = 3n-2$

von Sm/2 auf (3n/2-1)

ist das vielleicht   von Sm/2 auf (3m/2-1)   ?

Comments

Ne, in den Lösungen steht (3n/2 -1), wie man von S_m/2 darauf kommt, verstehe ich leider auch nicht, ist doch die Folge Sn = 3n - 1

---

Nur mit dem Korrektur Vorschlag von Mathef macht das alles Sinn. So wie Du es aufgeschrieben hast, ist es falsch.

---

Es steht so in den Lösungen, hier ein Screenshot:

Text erkannt:

Induktionsanfang:
$\begin{array}{l} T_{1}=1 \leq S_{1}=3 \cdot 1-1=2, \\ T_{2}=2 \leq S_{2}=3 \cdot 2-1=5 \end{array}$
Induktionsschluss:
Unter der Annahme der Korrektheit für alle $n=2^{i}, i \leq j, n>0$, ergibt sich der Induktionsschritt von $n=2^{i}$ nach $m=2 n=2^{i+1}$ :
$T_{m}=2 \cdot T_{m / 2}+1 \leq 2 S_{m / 2}+1=2 \cdot(3 n / 2-1)+1=3 n-2+1=3 n-1$
Für $n \neq 2^{i}, i \in \mathbb{N}$, ersetzen wir $n$ durch die nächstgrößere Zweierpotenz und erhalten genau 1 weitere Rekursionsebene.
Es gilt also jeweils $T_{n} \leq S_{n}=O(n)$.

---

Das ist falsch. Die Induktions Behauptung muss doch $$T_m \leq S_m$$ sein.