Vollständige Induktion mit 2 Variablen und einer Potenz ( k - beschränkte Bäume, Informatik)

Neue Frage »

Ina_93 Auf diesen Beitrag antworten »
Vollständige Induktion mit 2 Variablen und einer Potenz ( k - beschränkte Bäume, Informatik)
Meine Frage:
Hallo,
ich helfe gerade meinem Mitbewohner bei einer Aufgabe, welche durch die Vollständige Induktion zu beweisen ist.
Hier die Aufgabe:
Es sei ein k-beschränkter Baum (T) der Höhe h gegeben.
a) Beweisen Sie mittels vollständiger Induktion über die Höhe h: T besitzt höchstens Knoten.

Meine Ideen:
Ich hab mir natürlich auch schon selber Gedanken gemacht und zwar:
1. Der Induktionsanfang


h=1


somit ist der Induktionsanfang schon mal okay, da 1>0

2. Induktoinsschritt
2.1 Induktionsvoraussetzung

2.2 Induktionsbehauptung

2.3 Induktionsbeweis




...


Das waren soweit meine eigenen Gedanken, da ich aber vorher noch nicht mit der vollständigen Induktion gearbeitet habe, kann ich nicht beurteilen in wie weit das schon mal richtig ist oder ob es komplett falsch ist.

Vielen Dank im Voraus :-)
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

du verwendest im ganzen Post das falsche Ungleichungszeichen.


Zitat:
unglücklich
Schau dir das doch bitte nochmal genau an, das ist grober Unfug.


Denke auch an die geom. Summenformel in Bezug auf das
Zitat:


Und im Ind. schritt musst du dir überlegen wieviele Knoten maximal dazukommen wenn der Baum eine um eins größere Höhe hat.
Sinnvoll kann auch sein sich zu überlgen wie der Baum mit den meisten Knoten aussieht.
Ina_93 Auf diesen Beitrag antworten »



Weswegen ist das denn falsch?


Wenn der Baum um h wächst, dann kommen k Knoten dazu?

Ich bin selbst nicht all zu gut in Mathe, nur so neben bei.
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Weswegen ist das denn falsch?
Elementare Bruchrechenregeln:



Zitat:
Wenn der Baum um h wächst, dann kommen k Knoten dazu?
Das war zum Einen nicht das was ich gefragt hab, zum Anderen ist es falsch.


Zitat:
Ich bin selbst nicht all zu gut in Mathe, nur so neben bei.
Was soll mir das sagen?
Ina_93 Auf diesen Beitrag antworten »

Zitat:
Ich bin selbst nicht all zu gut in Mathe, nur so neben bei.

Ich wollte dir damit nur sagen, dass es bei mir auch mit einfacheren Sachen etwas hakt und wollte damit um etwas Nachsicht beten ^^

Zitat:
Das war zum Einen nicht das was ich gefragt hab, zum Anderen ist es falsch.

Es ist ja nett, dass du mir sagst das es falsch ist. Aber vielleicht könntest du mir ein paar Tipps für den richtigen Lösungsweg geben?
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Ich wollte dir damit nur sagen, dass es bei mir auch mit einfacheren Sachen etwas hakt und wollte damit um etwas Nachsicht beten ^^

Dann ist es doch gerade sinnvoll an den "einfachen" Sachen zu arbeiten.
Und meiner Erfahrung nach ist "ich bin nicht gut in Mathe" sehr oft schlicht eine billige Ausrede um sich nicht anzustrengen und /oder eine selbsterfüllende Prophezeiung.

Zitat:
Aber vielleicht könntest du mir ein paar Tipps für den richtigen Lösungsweg geben?
Das habe ich bereits in meinem ersten Post getan.

Insbesondere dass:
Zitat:
Und im Ind. schritt musst du dir überlegen wieviele Knoten maximal dazukommen wenn der Baum eine um eins größere Höhe hat.
Sinnvoll kann auch sein sich zu überlgen wie der Baum mit den meisten Knoten aussieht.
Mal dir das halt mal z.B. im Fall k=2 auf.

Vielleicht hilft nach dem Zeichnen auch der Tipp weiter:
Zitat:
Denke auch an die geom. Summenformel in Bezug auf das
Zitat:

 
 
Captain Kirk Auf diesen Beitrag antworten »

Scheinbar war meine Nachsicht zu wenig:
.onlinemathe.de/forum/Vollstaendige-Induktion-mit-2-Variablen-und-einer-P


Und der Vorzeichenfehler ist immer noch drin. Da ist halt dann irgendwann auch nicht mehr zu helfen.
Oder wenn man nicht mehr weiß ob man Ina oder Lucy heißt.
Ina_93 Auf diesen Beitrag antworten »

Ich heiße Ina, nur war der Name schon vergeben und ich dachte, dass ich dann meinen Spitznamen angebe (Aber wenn du auf dem Profil nachschaust, dann siehst du auch, dass dort mein richtiger Name angeben ist)^^
Wie gesagt, ich sitze nicht alleine vor der Aufgabe und wir wollten uns evtl. noch einen anderen Lösungsansatz anschauen.

Aber danke, dass du auf den Vorzeichenfehler aufmerksam gemacht hast.
RavenOnJ Auf diesen Beitrag antworten »
RE: Vollständige Induktion mit 2 Variablen und einer Potenz ( k - beschränkte Bäume, Informatik)
Es läuft doch darauf hinaus zu zeigen, dass . Da gibt es einen einfachen Trick, um das zu zeigen. Man kann das natürlich auch mit vollständiger Induktion machen. Es wäre zu überlegen, wieviel Knoten es in der h-ten Schicht höchstens gibt. Dies lässt sich einfach angeben, da die Knotenzahl von Schicht zu Schicht um höchstens den Faktor k wächst. Danach kann man mit vollständiger Induktion weiter machen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »