analytische Formel

[XXXNA]

Hi,

ich bin ja nun am Studieren. In Informatik sollen wir eine "analytische" Formel für die rekursive Funktion T(1) = 1, T(2n hoch n) = 2 T(2 hoch n-1) + 1 herleiten. Das ist weiter nicht das Problem:

T(2^n) = 2 * (2^n + 2^(n-1) + 2^(n-2)… + 1) + 1

= 2 * Summenzeichen von i=0 bis n von 2^(n-i) ) + 1

Meine Frage: Ist dies eine analytische Formel oder muss ich das Summenzeichen noch in einen Ausdruck, der nur von n abhängt zerlegen?

Thx schon jetzt für eure Antworten.

 

[Macross]

gibt es nicht Mathe Foren? Da wird einem mit sicherheit besser geholfen als in nem game Forum

 

[Osbes]

Hier gibt es doch ebenso Studenten, welche ein Mathestudium belegt haben, oder in ihrem Studium regelmäßig von der Mathematik begleitet werden (z.B. Physiker).

Wie habt ihr denn analytische Formeln definiert ?
Als analytische Funktion oder als eine Funktion welche das Ergebnis von F ohne Rekursion bestimmt ?

Ist n ein Element der natürlichen Zahlen ?
Ist T nur für 1 und 2*n^n (mit n Element der natürlichen Zahlen) definiert ?

 

[Mooff]

Ich denke du musst das Summenzeichen noch wegbekommen.

 

[XXXNA]

Denke, ich hab´s nun. Siehe Anhang. Meint ihr, das passt so?



Warum ist .doc als Format für den Anhang erlaubt und docx nicht? grrr^^

 

[Osbes]

Nur ist die Formel falsch.

Rekursion:
T(1) = T(2^0) = 1
T(2^1) = 2 * T(1) + 1 = 3

Deine Formel:
T(2^1) = 4 * ( 1 * ( 1 + 1) / 2) + 1 = 4 * 1 + 1 = 5 =!= 3
Es könnte auch sein, das du dort 2 ^ x rechnest, das kann ich nicht erkennen, jedoch kommt dann immernoch 5 raus.
T'(2^1) = 4 ^ ( 1 * ( 1 + 1) / 2) + 1 = 4^1 + 1 = 5 =!= 3

Dein Induktionsbeweis funktoniert daher auch nur, weil schon die Summe falsch ist und deine Induktionsannahme falsch ist (der kleine Gauß beginnt bei k = 1 und nicht k = 0).
Außerdem fehlt mir da ein wenig das + 1 in deiner Auflistung und daher ist auch die 2 nicht gut ausgeklammert, denn

T(2^n) ist nicht
2 * (2^n + 2^n-1 + … + 1) + 1
sondern
2 * (2 * ( 2 * ( 2 * ( 2 * ... (2 * 0 + 1) ... ) + 1) +1) +1) + 1) + 1

T(2^1) ist dann also
2 * ( 2 * 0 + 1 ) + 1 = 4 * 0 + 2 + 1 = 4 * 0 + 3 = 3
Und T(2^2) ist dann
2 * (2 * ( 2 * 0 + 1 ) + 1) + 1 = 4 * ( 2 * 0 + 1 ) + 3 = 8 * 0 + 4 + 3 = 7
Und T(3^2) ist dann
2 * (2 * (2 * ( 2 * 0 + 1 ) + 1) + 1) + 1 = 4 * (2 * ( 2 * 0 + 1 ) + 1) + 3 = 8 * ( 2 * 0 + 1 ) + 1) + 7 = 16 * 0 + 8 + 4 + 2 + 1 = 15

Und nochmal deutlicher aufgelistet:
T(2^0) = 2^0
T(2^1) = 2^0 + 2^1
T(2^2) = 2^0 + 2^1 + 2^2
T(2^3) = 2^0 + 2^1 + 2^2 + 2^3
T(2^4) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4
T(2^5) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5
T(2^6) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6
T(2^7) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7
T(2^8) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8

Man könnte es jetzt mit den Binärzahlen vergleichen, da immer alle addiert werden und wir wissen, dass
2^3 + 2^2 + 2^1 + 2^0 = 2^4 - 1
ist
also ist deine gesuchte Formel

2^(n+1) - 1

 

[XXXNA]

Danke dir, Osbes. Hatte einen Denkfehler drin, weil ich 2^0 nicht richtig in die Summe mit einberechnet habe. Deines ist auf jeden Fall richtig. Werd das noch schnell formal aufschreiben und die Herleitung aufstellen und das passt´s. Danke

 

[-Admi-]

Denke, ich hab´s nun. Siehe Anhang. Meint ihr, das passt so?

Warum ist .doc als Format für den Anhang erlaubt und docx nicht? grrr^^

Nur um das aufzugreifen...weil Office 2007 ist

Ne im Ernst...es hat einfach vor dir noch nie jemand gebraucht ^^