Hi!
Hat jemand nen Tipp zur Induktion?

MfG

Gibt es die Aufgaben online? Dann würde ich mir sie auch gerne angucken (:

http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0910/AuD/sec/AuD09aufg1.pdf

Hat jemand nen Tipp zur Induktion?

Schau dir die Aufgabenstellung genau an.
Schau, ob das für n=0 und n=1 stimmt (und begründe es.)
Und dann versuch, es für n+1 zu beweisen.

Im Prinzip brauchst du nur den simplen Ansatz zu finden, Rest ist Formel-Umstellerei.

also für n=0 und n=1 sehe ich durch einsetzen, dass es stimmt.
wenn ich aber n+1 in die Induktionsvoraussetzung [latex]a^n +\frac{1}{a^n}[/latex] einsetze, habe ich [latex]a^{n+1} +\frac{1}{a^{n+1}}[/latex] … und wie ich das jetzt beweisen kann verstehe ich leider nicht.
mfg

+
So, das reicht nun an Tipps ;-)

was :D

Ich bin bei diesem ersten Blatt total verloren. :/

Könnte mir jemand einbisschen weiterhelfen? Da ich nicht in den Vorlesungen sein konnte(was sich in Zukunft ändern wird) weiss ich nichtmal wie ich z.B. bei der zweiten Aufgabe ansetzen muss. Was heisst überhaupt "von welcher Größenordnung"? Ich soll das in groß oder klein o Notation angeben? Wie komme ich auf die entsprechenden o-Funktionen, sofern diese überhaupt gefragt sind?

die folien zu VL2 sollten dir helfen.
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0910/AuD/
Zu der Größenordnung: Du suchst eine Funktion die ähnlich schnell wächst wie die gegebene, aber simpler ist. soweit verstehe ich das….allerdings habe ich zu der aufgabe 1.2.1 und 1.2.2 auch noch ne frage:
wenn ich die summe einfach nur ausschreibe habe ich ja ein polynom eines bestimmten grades. wenn ich es allerdings mit der gaußschen summenformel unschreibe bekomme ich auch ein polynom, aber mit einem um 1 höheren grad. wenn ich es zeichnen lasse, scheint auch die zweite variante die richtige zu sein aber steht das nicht im widerspruch zu dem satz "ist p(n) ein Polynom von Grad m, dann gilt: [latex]p \epsilon O(n^m)[/latex]" ?

http://alda.iwr.uni-heidelberg.de/index.php/Effizienz#Landau-Symbole

Hilft stellenweise viel besser als das Skript.

http://alda.iwr.uni-heidelberg.de/index.php/Effizienz#Landau-Symbole

Hilft stellenweise viel besser als das Skript.

Die Präsentationsfolien sind KEIN Skript und sollten das auch nie sein!
Es gibt das Buch von Corman/Leiserson/… da steht auch alles drin, und die Vorlesung nicht zu besuchen ist sicher sehr ungeschickt!
Das Bachelorstudium in Hamburg ist KEIN Fernstudium (sollte es nie sein)!!

http://alda.iwr.uni-heidelberg.de/index.php/Effizienz#Landau-Symbole

Hilft stellenweise viel besser als das Skript.

Die Präsentationsfolien sind KEIN Skript und sollten das auch nie sein!
Es gibt das Buch von Corman/Leiserson/… da steht auch alles drin, und die Vorlesung nicht zu besuchen ist sicher sehr ungeschickt!
Das Bachelorstudium in Hamburg ist KEIN Fernstudium (sollte es nie sein)!!

Wenn ich anfangen würde aufzuzählen was das Studium in Hamburg (und vielen anderen Unis) nicht ist aber eigentlich (immer) sein sollte würde ich wohl die AD Klausur verpassen.

aufgabe 1.2.1 und 1.2.2:
wenn ich die summe einfach nur ausschreibe habe ich ja ein polynom eines bestimmten grades. wenn ich es allerdings mit der gaußschen summenformel unschreibe bekomme ich auch ein polynom, aber mit einem um 1 höheren grad. wenn ich es zeichnen lasse, scheint auch die zweite variante die richtige zu sein aber steht das nicht im widerspruch zu dem satz "ist p(n) ein Polynom von Grad m, dann gilt: [latex]p \epsilon O(n^m)[/latex]" ?

kann dazu bitte jemand was sagen?

[latex] \frac{1-x^{n+1}}{1 - x} = \frac{1}{1-x} + \frac{x^{n+1}}{1-x} [/latex] ist kein Polynom vom Grad n+1.

Ich würde einmal
[latex]a^n+\frac{1}{a^n} [/latex] mit  [latex]a+\frac{1}{a} [/latex] multiplizieren und das Ergebnis genau ansehen….
Was das mit der Induktion zu tun hat sollte herauszufinden sein!

Nur nicht verzweifeln!

wenn ich die summe einfach nur ausschreibe habe ich ja ein polynom eines bestimmten grades

Koenntest du mir sagen, wie ich das mache? Oder wie verwandel ich allgemein die Reihe in ein Polynom?

also 1. ist 1^m + 2^m + … + n^m.
2. ist m^1 + m^2 + … m^n.
ob das jetzt beides tatsächlich polynome sind bin ich mir noch nicht so sicher xD

danke theorinix =)

Schau dir die Aufgabenstellung genau an.
Schau, ob das für n=0 und n=1 stimmt (und begründe es.)
Und dann versuch, es für n+1 zu beweisen.

Im Prinzip brauchst du nur den simplen Ansatz zu finden, Rest ist Formel-Umstellerei.

Umstellen reicht nicht ganz, kleiner Tip:
Du bekommst etwas heraus, wo Du kombinieren musst, so nach dem Schema:
Wenn das Ergebnis (Z) eine ganze Zahl sein soll, und B eine ganze Zahl ist, dann muss auch A eine ganze Zahl sein, für
Z = A + B

Vielleicht das unten nochmal ansehen….

Ich würde einmal
[latex]a^n+\frac{1}{a^n} [/latex] mit [latex]a+\frac{1}{a} [/latex] multiplizieren und das Ergebnis genau ansehen….