Hallo.
Ich möchte gerne beweisen, dass gilt:
S(n,2) = 2^(n-1)-1 für n>=2
hierbei kenne ich die n. Definition Formeln S(n,n) = S(n,1)= 1 sowie S(n,k)=S(n-1,k-1)+k*S(n-1,k)
Da kam mir die vollständige Induktion in den Sinn.
Ich setze n=2 ein, erhalte
S(2,2) = 1 = 2^(2-1) =1
Stimmt also.
Für n=n+1 gilt nun also
S(n+1,2)=((n+1)-1-1,2-1)+2S((n+1)-1,2) = S(n,1) +2S(n,1) = 1+2*1 = 3 = 2^(n+1-1)-1 = 2^n - 1.
Hier kann ich aber nirgends die Induktionsannahme wo einsetzen, also sage ich einfach, dass zu zeigen ist, dass 3 = 2^n - 1 eine Lösung hat
3= 2^n-1
4 = 2^n ||ln ||: ln2
n = ln4/ln2 =2
Die Induktionsverankerung ist also ab n>= 2
Ist das noch ein halbwegs akzeptabler Beweis oder ist der verpfuscht? Falls der inakzeptabel sein sollte, würde ich mich auch über eine Richtigstellung freuen.
Grüße,
McMike