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.