Informatiker Board | Druckvorschau: asymptotische Verhalten beweisen

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- asymptotische Verhalten beweisen (http://www.informatikerboard.de/board/thread.php?threadid=2991)

Geschrieben von Hang-over am 01.05.2016 um 10:24:

asymptotische Verhalten beweisen

Meine Frage:
Rekursiongleichung beweisen

T(1) =1
T(n)=T(n-1)+2n, n=>2

Hinweis T(n)=2*(n(n+1)/2)

Meine Ideen:
Ich weiß nicht wie ich hier vorgehen soll, hab schon einige Beweise mir angeguckt wie die da vorgehen, aber da wird immer zuerst eine Obere Schranke vermutetet
Und dann die Vermutung in T(n)<= c * (Vermutung) eingesetzt aber wie kommt man denn drauf

Wäre super wenn mir hier jemand erklären könnte wie das funktioniert

Geschrieben von eulerscheZahl am 01.05.2016 um 10:57:

t(1) = 1
t(2) = 4+t(1) = 4+1 = 5
t(3) = 6+t(2) = 6+4+1 = 11
t(4) = 8+t(3) = 8+6+4+1 = 19

Hier werden (bis auf die letzte Zahl) immer geradzahlige Zahlen addiert.
Es sieht aus, als wäre $[latex]t_n = \sum_{i=1}^n2\cdot i - 1= n\cdot(n+1)-1[/latex]$ .
Lässt sich mit Induktion auch beweisen.

Geschrieben von Hang-over am 01.05.2016 um 11:25:

Deine Summe ist falsch in der Aufgabe T(n) = 2* (Summe von i=1 bis n) i

Geschrieben von Hang-over am 01.05.2016 um 11:26:

Also muss man das einfach nur mit induktion
Aber im Internet hab ich immer Beweise gefunden mit o Notation so muss das doch gehen ??

Geschrieben von Hang-over am 01.05.2016 um 11:37:

vred.bioinf.uni-sb.de/prog2_ss04/lectures/rekursion.pdf

Geschrieben von eulerscheZahl am 01.05.2016 um 19:47:

Du hast in der Lösung auch eine andere Formel als ich (beachte die -1).
Die exakte Formel kann man mit Induktion zeigen. Für die nicht exakte geht das natürlich nicht.