Vollständige Induktion der Formeln, mit Rekursion der Stirling-Zahlen und die Verankerungen Sn,n = Sn,1 = 1

Question

Aufgabe

In der Vorlesung wurden kombinatorische Begründungen für die Formeln Sn,2 = 2^n–1  – 1 und S tief n,n–1 = (n über 2) für alle n ≥2 besprochen.
(a) Beweisen Sie die Formeln noch einmal mit vollständiger Induktion, wobei nur die Rekursion der Stirling-Zahlen und die Verankerungen Sn,n = Sn,1 = 1 verwendet werden

Problem/Ansatz:

Mein Problem hierbei ist, dass ich beim Induktionsschritt nicht auf die Lösung komme. Ich habe mehrere Ansätze probiert, die anscheinend keinen Sinn machen, wie z.B.

I.A. S tief n,n = S tief n,1 = 1

I.B. |S tief n,k| = |S tief n-1,k-1| + k |S tief n-1,k|

I.S. S tief n,n -> A tief n,2

Ich komme einfach nicht weiter. ich danke im voraus

Answer 1

Ich verstehe das so, dass du die zunächst die Formel

S_n,2=2^n-1 -1 per. Induktion beweisen sollst.

Also zu prüfen :  I.A. (n=2)   S_2,2=2^2-1 -1=2-1=1

Das ist die Verankerung, die du ja benutzen darfst.

I.B. Unter der Vor, dass die Formel für n gilt

        gilt auch S_n+1,2=2ⁿ -1

Benutze dazu die Rekursion:

S_n+1,2 =   S_n,1 + 2 * S_n,2  = 1 +  2 * (2^n-1 - 1 )

= 1 + 2ⁿ - 2 = 2ⁿ - 1.  

Also stimmt die Formel für n+1. q.e.d.

Entsprechend mit der anderen. S_n,n-1 = (n über 2) = n(n-1) / 2